[Baekjoon] 12887_경로 게임

Gold V

문제(출처: https://www.acmicpc.net/problem/12887)

---

< 경로 게임 >

 

문제 풀이 

 

행의 개수가 항상 2이므로 0번째 행과 1번째 행에서 시작한 결과를 비교한다. 최단거리는 오른쪽으로 갈 수 있다면 오른쪽으로 이동하고, 이동할 수 없다면 위 또는 아래로 이동한다. 총 (격자판의 칸 수 - 검은색 칸 수 - 이동 칸 수)를 구한다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class _12887_ { // 경로 게임
	static boolean arr[][];
	static int dx[] = { 0, -1, 1 };
	static int dy[] = { 1, 0, 0 };

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int m = Integer.parseInt(bf.readLine());

		arr = new boolean[2][m];

		int black = 0;
		for (int i = 0; i < 2; i++) {
			String str = bf.readLine();
			for (int j = 0; j < m; j++) {
				if (str.charAt(j) == '#') {
					arr[i][j] = true;
					black += 1;
				} else {
					arr[i][j] = false;
				}
			}
		}

		int result = 0;

		if (!arr[0][0]) {
			int cnt = check(0, 0);
			if (result < 2 * m - cnt - black) {
				result = 2 * m - cnt - black;
			}
		}

		if (!arr[1][0]) {
			int cnt = check(1, 0);
			if (result < 2 * m - cnt - black) {
				result = 2 * m - cnt - black;
			}
		}
		System.out.println(result);
	}

	private static int check(int x, int y) {

		int cnt = 1;

		while (y < arr[0].length - 1) {
			for (int i = 0; i < 3; i++) {
				int a = x + dx[i];
				int b = y + dy[i];
				if (a >= 0 && a < 2 && b >= 0 && b < arr[0].length && !arr[a][b]) {
					cnt += 1;
					if (b == arr[0].length - 1) {
						return cnt;
					}
					x = a;
					y = b;
					break;
				}
			}
		}
		return cnt;
	}
}

변수)
m : 열의 개수
arr : 격자판 정보
black : 검은색 칸 수
str : 행 정보
result : 바꿀 수 있는 하얀색 칸의 개수의 최댓값 
cnt : 경로 칸 수

 

열의 개수를 입력받는다. 격자판 정보를 입력받아 검은색일 때 true로 저장하고 하얀색일 때 false로 저장한다. 격자판 정보를 저장하면서 검은색 칸 수를 구한다. [0,0] 번째가 하얀색 칸이라면 check 함수를 호출한다. [1,0] 번째가 하얀색 칸이라면 check 함수를 호출한다. 반환 값으로 받은 경로 칸 수와 검은색 칸 수를 총 격자판 수에서 뺀다. 이 값이 바꿀 수 있는 하얀색 칸의 수이므로 result와 비교해 최댓값을 구한다.     

 

최종 result를 출력한다.

 

check(int x, int y)

가장 오른쪽 열에 도착하기 전까지 다음 과정을 반복한다.

 

오른쪽으로 이동 가능 하다면 오른쪽으로 이동한다. 오른쪽으로 이동 불가능하다면 위 또는 아래로 이동한다. 이때 이동 칸 수를 센다. 만약 가장 오른쪽 열에 도착했다면 바로 종료한다.

---

처음에는 방문처리를 활용하여 경로를 구한 후 검은색 칸이 아니고 방문하지 않은 곳을 찾아 답을 구하는 방식으로 구현했다. 이 경우 틀렸습니다를 받았고 미리 수를 세는 것과 어디서 차이가 발생했는지 잘 모르겠다.

 

---