[백준] code.plus(BFS,JAVA)14226번, 이모티콘

문제 링크

14226번: 이모티콘

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에서 BFS를 통하여 문제를 해결하였습니다.

 

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처 : https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 화면에는 1개에 이모티콘이 입력되어 있습니다.

2. 연산 3가지를 통해서 이모티콘 개수를 수정할 수 있습니다.

3. 모든 연산은 1초가 소모된다.

4. 입력되는 이모티콘 개수가 되는 최소 소요 시간을 결과로 출력합니다.

 

사용되는 배열

visited[i][j] : i의 이모티콘의 개수, j는 클립보드에 저장된 이모티콘 개수에 방문했는지 확인하는 배열

 

알고리즘을 구현하기 위해 저는 BFS(너비 우선 탐색)을 통해 구현하였습니다.

 

문제에서 가르키는 연산에 대해서 해석해보겠습니다.

 

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장합니다.

클립보드 값이 현재 이모티콘 값이 아닌 경우 복사 가능!

클립보드 값을 현재 이모티콘 값으로 변경합니다.

 

2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.

클립보드 값을 현재 이모티콘 개수에 더한다.

 

3. 화면에 있는 이모티콘 중 하나를 삭제한다.

현재 이모티콘 개수에서 -1을 한다.

 

BFS 탐색을 통해 가장 먼저 이모티콘에 개수가 되었을 때가 최소 시간입니다.

 

예제입력2으로 BFS가 진행되는 과정을 보여드리겠습니다.

S = 4

초기 화면

화면 이모티콘 : 1클립보드 : 0소요시간 : 0DP[1][0] = True탐색

	화면 이모티콘	클립보드	소요시간
연산1	1	1	1
연산2	x	x	x
연산3	0	0	1

연산 2는 이모티콘에 클립보드 값을 더한 것이 DP[1][0]으로 이미 진행했기 때문에 x로 표시하였습니다.

 

1) 연산 1에 대하여 탐색을 진행하면

화면 이모티콘 : 1클립보드 : 1소요 시간 : 1DP[1][1] = True

	화면 이모티콘	클립보드	소요시간
연산1	x	x	x
연산2	2	1	2
연산3	0	1	2

연산1은 클립보드와 화면 이모티콘 개수가 같아서 복사해도 의미가 없으므로 x로 표현하였습니다.

 

2) 연산3에 대한 탐색을 진행하면

화면 이모티콘 : 0

클립보드 : 0

소요 시간 : 1

DP[0][0] = True

	화면 이모티콘	클립보드	소요시간
연산1	x	x	x
연산2	x	x	x
연산3	x	x	x

연산1과 연산2는 위와 동일하며 연산 3은 이모티콘 개수가 -1이 될 수 없으므로 x로 표현하였습니다.

 

1)) 1)에 대한 연산2을 탐색하면

화면 이모티콘 : 2

클립보드 : 1

소요 시간 : 2

DP[2][1] = True

	화면 이모티콘	클립보드	소요시간
연산1	2	2	3
연산2	3	1	3
연산3	x	x	x

연산3은 DP[1][1]이 탐색되었기 때문에 진행하지 않습니다.

 

2)) 1)에 대한 연산3을 탐색하면

화면 이모티콘 : 0

클립보드 : 1

소요 시간 : 2

DP[0][1] = True

	화면 이모티콘	클립보드	소요시간
연산1	x	x	x
연산2	x	x	x
연산3	x	x	x

위 내용들을 이해하셨으면 다 x가 나오는지 이해했을 것이라고 생각하고 넘어가겠습니다.

 

1))) 1))에 대한 연산1을 탐색하면

화면 이모티콘 : 2

클립보드 : 2

소요 시간 : 3

DP[2][2] = True

	화면 이모티콘	클립보드	소요시간
연산1	x	x	x
연산2	4	2	4
연산3	1	2	4

연산 2에서 입력값에서 찾는 화면 이모티콘 개수를 구하였으므로 탐색을 종료합니다.

 

처음 입력값과 동일한 이모티콘 개수에 도달할 때가 최소 소요시간입니다.

 

최소 소요시간 4가 결과로 출력됩니다.

 

 

문제를 해결한 알고리즘의 과정입니다.

1. 입력값 S를 저장합니다.

2. BFS(너비 우선 탐색)에서 연산1, 2, 3을 이용하여 탐색합니다.

3. S와 동일한 이모티콘 개수를 가장 먼저 도달한 시간을 최소 시간으로 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• BFS탐색과 연산1,2,3을 이용하여 이모티콘 개수를 출력하는 최소 시간을 구하는 bfs함수를 사용하였습니다.
• BufferedWriter에 BFS를 통해 얻은 최소 시간을 저장하였습니다.
• BufferedWriter에 저장된 값을 결과로 출력하였습니다.

• bfs 함수는 연산1,2,3과 BFS를 이용하여 탐색하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	//BFS에 큐가 사용할 생성자
	static class emoticon{
		int count, clipboard, point;	//시간, 클립보드, 이모티콘 개수
		public int getCount() {
			return count;
		}
		public int getClipboard() {
			return clipboard;
		}
		public int getPoint() {
			return point;
		}
		public emoticon(int count, int clipboard, int point) {
			this.count = count;
			this.clipboard = clipboard;
			this.point = point;
		}
	}
	static int S;
	static boolean[][] visited = new boolean[10001][1001];	//탐색 확인 배열
	public static void main(String[] arg) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값을 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값을 출력하는 BufferedWriter
		S = Integer.parseInt(br.readLine());		//입력값 S 저장
		int result = bfs();		//BFS함수 실행 및 최소 시간 저장
		bw.write(result + "\n");		//최소 시간 BufferedWriter 저장
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//BFS에서 연산1,2,3을 이용하여 최소 시간을 탐색하는 함수
	static int bfs() {
		Queue<emoticon> queue = new LinkedList<emoticon>();		//BFS에 사용할 큐
		queue.add(new emoticon(0, 0, 1));		//초기 화면 큐에 저장
		visited[1][0] = true;		//초기 화면 탐색 완료
		while(!queue.isEmpty()) {
			emoticon temp = queue.poll();
			int count = temp.getCount();
			int clipboard = temp.getClipboard();
			int point = temp.getPoint();
			if(point == S) 		//입력값 S 도달 완료시
				return count;
			
			if(clipboard != point && clipboard <2001)	//연산1.
				queue.add(new emoticon(count+1, point, point));
			
            		//연산2.
			if(clipboard < 1001 && !visited[point + clipboard][clipboard] ) {
				visited[point + clipboard][clipboard] = true;
				queue.add(new emoticon(count+1, clipboard, point + clipboard));
			}
            
            		//연산3.
			if(point>0 && clipboard<1001 && !visited[point-1][clipboard] ) {
				visited[point-1][clipboard] = true;
				queue.add(new emoticon(count+1, clipboard, point-1));
			}	
		}
		return 0;
	}
}