[백준 / BOJ 14714] 홍삼게임(Easy)

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

14714번: 홍삼 게임 (Easy)

 

BFS를 사용한 문제다.

 

일단 방문 체크를 할 수 있는 배열을 만들었다. 이름은 쉽게 map으로.

초기에 map은 (지목권 A, 지목권 B)를 체크했다. 예를 들어 3번째 지목에 2번 사람이 지목권 A를 가지고, 4번 사람이 지목권 B를 가진다면, map의 (2, 4)는 3이다.

 

이렇게 만든 이유는 어떠한 (A, B)의 경우가 나왔을 때, 그 이후에 진행될 수 있는 경우의 수가 항상 똑같기 때문이다. 아까처럼 (2, 4) 상태이고 B가 움직일 차례에 DB가 1이라면? 다음에 나올 수 있는 경우의 수는 (2, 3)과 (2, 5) 둘 밖에 없다. 따라서 한 번 나왔던 경우는 그 다음에 다시 확인할 필요가 없는 것이다.

 

이를 통해 다음과 같은 답을 제출했지만 틀렸다.

 

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int A = Integer.parseInt(st.nextToken()) - 1; // 첫번째 지목
		int B = Integer.parseInt(st.nextToken()) - 1; // 두번째 지목
		int DA = Integer.parseInt(st.nextToken());
		int DB = Integer.parseInt(st.nextToken());
		
		int[][] map = new int[N][N];
		
		Queue<int[]> que = new LinkedList<>();
		
		que.offer(new int[] {A, B, 1});
		map[A][B] = 1;
		
		while(!que.isEmpty()) {
			int[] cur = que.poll();
			int a = cur[0];
			int b = cur[1];
			int cnt = cur[2];
			
			if(cnt % 2 == 1) {
				int a_left = a - DA;
				if(a_left < 0) a_left += N;
				int a_right = a + DA;
				if(a_right >= N) a_right -= N;
				
				if(map[a_left][b] == 0) {
					map[a_left][b] = cnt + 1;
					que.offer(new int[] {a_left, b, cnt+1});
				}
				if(map[a_right][b] == 0) {
					map[a_right][b] = cnt + 1;
					que.offer(new int[] {a_right, b, cnt+1});
				}
			} else {
				int b_left = b - DB;
				if(b_left < 0) b_left += N;
				int b_right = b + DB;
				if(b_right >= N) b_right -= N;
				
				if(map[a][b_left] == 0) {
					map[a][b_left] = cnt + 1;
					que.offer(new int[] {a, b_left, cnt+1});
				}
				if(map[a][b_right] == 0) {
					map[a][b_right] = cnt + 1;
					que.offer(new int[] {a, b_right, cnt+1});
				}
			}
		}
		
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < N; i++) {
			if(map[i][i] != 0 && min > map[i][i]) min = map[i][i]; 
		}
		
		if(min == Integer.MAX_VALUE) System.out.println("Evil Galazy");
		else System.out.println(min - 1);
	}

}

 

 

왜 틀렸을까? 위 코드를 작성하면서 한 설명에 중요한 부분이 있다. 만일 A가 움직일 차례라면? 그러면 (2, 3), (2, 5)가 아니라 DA에 따라 달라진다. DA도 1이라고 생각해보자. 그러면 (3, 4)나 (1, 4)가 될 것이다. 즉, 지목권 A와 지목권 B의 조합만을 생각하면 안되고, 지금 어떤 지목권이 움직일 차례인지도 조건에 넣어줘야 한다. 이에 따라 map을 3차원 배열로 변경해 문제를 풀 수 있었다.

 

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int A = Integer.parseInt(st.nextToken()) - 1; // 첫번째 지목
		int B = Integer.parseInt(st.nextToken()) - 1; // 두번째 지목
		int DA = Integer.parseInt(st.nextToken());
		int DB = Integer.parseInt(st.nextToken());
		
		int[][][] map = new int[2][N][N];
		
		Queue<int[]> que = new LinkedList<>();
		
		que.offer(new int[] {A, B, 1});
		map[0][A][B] = 1;
		map[1][A][B] = 1;
		
		while(!que.isEmpty()) {
			int[] cur = que.poll();
			int a = cur[0];
			int b = cur[1];
			int cnt = cur[2];
			
			if(cnt % 2 == 1) {
				int a_left = a - DA;
				if(a_left < 0) a_left += N;
				int a_right = a + DA;
				if(a_right >= N) a_right -= N;
				
				if(map[0][a_left][b] == 0) {
					map[0][a_left][b] = cnt + 1;
					que.offer(new int[] {a_left, b, cnt+1});
				}
				if(map[0][a_right][b] == 0) {
					map[0][a_right][b] = cnt + 1;
					que.offer(new int[] {a_right, b, cnt+1});
				}
			} else {
				int b_left = b - DB;
				if(b_left < 0) b_left += N;
				int b_right = b + DB;
				if(b_right >= N) b_right -= N;
				
				if(map[1][a][b_left] == 0) {
					map[1][a][b_left] = cnt + 1;
					que.offer(new int[] {a, b_left, cnt+1});
				}
				if(map[1][a][b_right] == 0) {
					map[1][a][b_right] = cnt + 1;
					que.offer(new int[] {a, b_right, cnt+1});
				}
			}
		}
		
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < N; i++) {
			if(map[0][i][i] != 0 && min > map[0][i][i]) min = map[0][i][i];
			if(map[1][i][i] != 0 && min > map[1][i][i]) min = map[1][i][i];
		}
		
		if(min == Integer.MAX_VALUE) System.out.println("Evil Galazy");
		else System.out.println(min - 1);
	}

}

 

즉, 배열의 1차원은 A지목권이 이동하는지/B지목권이 이동하는지, 2차원은 A지목권의 위치, 3차원은 B지목권의 위치이다. map[0][2][4]는 A지목권이 이동해서 2가 되고, B지목권은 4에 남아있는 경우를 의미한다. 위 코드는 정답으로 인정받았다.