[KOITP] 출근

출    처 : http://koitp.org/problem/RIGHTDOWN/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	689	175 (25%)	160

문제

삼성이는 매일 출근을 한다. 도로는 아래 그림과 같이 가로 방향 도로가 $(H+1)$개, 세로 방향 도로가 $(W+1)$개가 바둑판 모양으로 배치되어 있다. 상성이네 집은 $(1,1)$이고, 회사는 $(H+1,W+1)$에 있다.
$(a,b)$는 위쪽에서 $a$번째, 왼쪽에서 $b$번째에 있는 교차로이다.

매일 같은 경로로 운전해간다면 졸음운전의 위험이 굉장히 높아진다. 따라서 아래와 같은 재미있는 방법으로 회사까지 가려고 한다.

• 항상 오른쪽, 또는 아래쪽으로 이동한다.
• 맨 아래와, 맨 오른쪽을 제외한 각 교차로에 ‘아’ 혹은 ‘오’가 적혀있다.
• ‘아’라고 적힌곳에 있다면, 아래로 가야한다. 또 ‘오’라고 적힌곳에 있다면 오른쪽으로 가야한다.
• 지나친 교차료의 ‘아’와 ‘오’는 다음날 서로 바뀐다. ‘아’를 지났다면, 다음날 그 교차로는 ‘오’로 바뀌어져 있다.

$N$번째 날의 출근 경로를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 $H,W,N$이 주어진다. $(1\le H,W\le 1,000,1\le N\le 10,000,000)$

두 번째 줄부터 $H$개 줄에 걸쳐 각 줄에 $W$개의 정수가 주어진다. 이 정수는 맨 아래와 오른쪽을 제외한 교차로에 적혀있는 ‘오’, ‘아’에 대한 정보이다. $0$은 ‘아’, $1$은 ‘오’를 의미한다.

출력

$N$번째 산책에서 가장 처음 도착하는 맨 아래, 또는 맨 오른쪽의 교차로를 $(i,j)$라 할 때, $i$와 $j$를 공백으로 구분하여 출력한다.

힌트

예제 입력

3 4 3
1 0 1 1
0 1 0 0
1 0 1 0

예제 출력

1 5

힌트

< Comment >

 해당 문제를 처음 보고 그냥 for 루프를 돌려봤었습니다. 그러나 당연하게도 시간 복잡도가 O(WHN)이 되어 시간에 맞추어 들어올 수 없었습니다. 사실 결과적으로 구하고자 하는것은 N번째 날의 출근 길이기 때문에, 길이 1번 방문할 때마다 Toggle 된다는 것에 주목하여 문제를 풀 수 있었습니다. 그 뒤로 BFS로도 구현했었는데, 속도가 느려서 오히려 그냥 3중 for 루프보다 느렸고, 따져보니 BFS를 이용하지 않아도 되었기 때문에 2중 for 루프를 이용하였습니다.

 문제에서 중요한 핵심은, 과연 이 지점을 몇 번이나 방문했는가 입니다. N 번째 날의 출근길은 N-1번째 날까지 삼성이가 지나갔을 것입니다. 일단 그렇기 때문에 시작 지점인 1, 1 지점(문제 풀때는 0, 0으로 놓고 풀었습니다) 에 N-1 을 넣어두고, 분배를 시작합니다. 어차피 오른쪽 혹은 아래로만 이동할 수 있기 때문에, 1, 1 지점에서 출발할 경우, 가는 방향이 토글되면서 결국 N-1번째 날까지, 우측으로 (N-1)/2 개 아래측으로 (N-1)/2 번 들어가게 됩니다. 물론 N-1값이 홀수인 경우에는 초기값이 0인지 1인지에 따라서 분배가 달라지지만 기본적인 사상은 이렇습니다.

 이를 0 ~ W, 0 ~ H 동안 루프를 돌면서 분배해 줍니다. 오른쪽 또는 아래쪽 이동이기 때문에, 위에서부터 차례대로 읽어도 무방합니다. 만약 여기서 분배되는 숫자가 0이라고 하면 그 루프는 종료해줍니다. 이렇게 되면, 각 지점을 방문한 횟수를 구하는데 O(WH)라는 시간밖에는 걸리지 않게 됩니다. 이후로는 그저 처음의 지점 상태로부터 짝수번 방문한 경우는 그대로, 홀수번 방문한 경우는 토글된 상태로 간다고 가정하여, 결과적으로 도착하는 지점만 구해주면 됩니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Commute {
	
	public static int H = 0;
	public static int W = 0;
	public static int N = 0;
	
	public static int map[][] = null;
	public static int count[][] = null;
	public static boolean isVisited[][] = null;

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());
		H = Integer.parseInt(st.nextToken());
		W = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		
		map = new int[H + 1][W + 1];
		count = new int[H + 1][W + 1];
		isVisited = new boolean[H + 1][W + 1];
		
		for (int i = 0 ; i < H ; i++) {
			
			st = new StringTokenizer(br.readLine());
			for (int j = 0 ; j < W ; j++) {
				
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
			
		count[0][0] = N - 1;
		for (int i = 0 ; i < H ; i++) {
			
			for (int j = 0 ; j < W ; j++) {
				
				if(count[i][j] == 0) {
					continue;
				}
				
				int m = count[i][j] / 2;
				
				int bigger = 0;
				int smaller = 0;
				if (count[i][j] % 2 == 0) {
					bigger = m;
					smaller = m;
				} else {
					bigger = m + 1;
					smaller = m;
				}
				
				if(map[i][j] == 0) {
					
					count[i + 1][j] += bigger;
					count[i][j + 1] += smaller;
				} else {
					
					count[i + 1][j] += smaller;
					count[i][j + 1] += bigger;
				}
			}
		}
		
		int i = 0;
		int j = 0;
		while (i != H && j != W) {
			
			if(count[i][j] % 2 == 0) {	// 짝수번 방문한 경우 : 그대로
				
				if(map[i][j] == 0) {
					i++;
				} else {
					j++;
				}
			} else {
				
				if(map[i][j] == 0) {
					j++;
				} else {
					i++;
				}
			}
		}
			
		bw.write("" + (i + 1) + " " + (j + 1));
		bw.flush();
		bw.close();
	}
}