백준 14226번

문제

https://www.acmicpc.net/problem/14226

알고리즘

1. bfs

풀이

1. BFS: 최소 시간를 구해야 하므로 BFS를 사용해야 합니다.

2. 상태 설계

“현재 화면에 있는 이모티콘 수”와 “클립보드에 복사된 이모티콘 수”의 조합

• 화면 5개 / 클립보드 2개
• 화면 5개 / 클립보드 3개

이 둘은 이후 가능한 행동이 완전히 달라지기 때문에 서로 다른 상태로 간주해야 합니다.

3. 방문처리 

visited[화면][클립보드]로 관리하면 모든 가능한 상태 조합을 추적할 수 있습니다.

코드

public class Main {

	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			int s = Integer.parseInt(br.readLine());
			boolean[][] visited = new boolean[2001][2001];
			Queue<int[]> q = new ArrayDeque<>();
			q.add(new int[]{1, 0, 0});
			visited[1][0] = true;

			while (!q.isEmpty()) {
				int[] cur = q.poll();
				int screen = cur[0], clip = cur[1], time = cur[2];

				if (screen == s) {
					System.out.println(time);
					return;
				}

				if (!visited[screen][screen]) {
					visited[screen][screen] = true;
					q.add(new int[]{screen, screen, time + 1});
				}

				if (clip > 0 && screen + clip < 2000 && !visited[screen + clip][clip]) {
					visited[screen + clip][clip] = true;
					q.add(new int[]{screen + clip, clip, time + 1});
				}

				if (screen > 1 && !visited[screen - 1][clip]) {
					visited[screen - 1][clip] = true;
					q.add(new int[]{screen - 1, clip, time + 1});
				}
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}