[BOJ 백준] 산책(5573) C++, Java

 

링크 : https://www.acmicpc.net/problem/5573

5573번: 산책

 

문제 설명 : 

상근이는 건강을 위해 산책을 하려고 한다.

상근이가 사는 마을은 아래 그림과 같이 가로 방향 도로가 (H+1)개, 세로 방향 도로가 (W+1)개가 바둑판 모양으로 배치되어 있다. 상근이네 집은 가장 왼쪽 위 교차로에 있으며, 이곳에서 산책을 시작한다.

(a,b)는 위쪽에서 a번째, 왼쪽에서 b번째에 있는 교차로이다. 예를 들어, 상근이네 집은 교차로 (1,1)에 있다.

상근이는 산책 경로가 매일 달라야 질리지 않고 산책을 할 수 있다고 생각한다. 따라서, (1,1)에서 (H,W)까지 H × W개 교차로에 오른쪽을 뜻하는 오 또는 아래를 뜻하는 아를 쓰고, 다음과 같은 규칙에 따라서 산책을 하기로 했다.

교차로에 쓰여 있는 문자가 오라면, 이 문자를 지우고 아를 쓴다. 그 다음에 오른쪽으로 진행한다. 만약, 교차로에 쓰여 있는 문자가 아라면, 이 문자를 지우고 오를 쓴뒤, 아래로 진행한다.

이렇게 산책을 하다가 가장 오른쪽이나 아래쪽 도로에 도착하면 산책을 종료한다.

상근이는 이런 방법으로 산책을 계속 한다면, N번째 산책 경로가 어떻게 될지 궁금해졌다. H, W와 각 교차로에 써놓은 글자가 주어졌을 때, N번째 산책 경로를 구하는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에 H, W, N이 주어진다. (1 ≤ H,W ≤ 1000, 1 ≤ N ≤ 107)

둘째 줄부터 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

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

Java코드 : 

import java.io.*;
import java.util.*;

// 산책 5573
public class Main {

	// 출력용 변수
	static StringBuilder sb = new StringBuilder();

	static int H, W, N;
	
	static int[][] map;

	// dp [i][j] : N-1 번 산책했을때, {i, j} 의 방문횟수
	static int[][] dp;
	

	public static void main(String[] args) throws IOException {
		// 1. 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		
		H = Integer.parseInt(st.nextToken());
		W = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
	
		map = new int [H+2][W+2];
		dp = new int [H+2][W+2];
		
		for (int i = 1; i <= H; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= W; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		

		// 2. dp 배열 구하기
		// N-1번 산책할때 교차로를 몇번 지나게 되는지
		//     0 아래   /  1 오른
		dp[1][1] = N - 1;
		int tmp;
		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= W; j++) {
				tmp = dp[i][j];

				// 2-1. 교차로에 '오'
				if (map[i][j] == 1) {
					// 오른쪽에 횟수 더해주기
					dp[i][j + 1] += (tmp / 2);

					// 아래에 횟수 더해주기 
					dp[i + 1][j] += (tmp / 2);

					// 방문횟수 홀수면 보정
					if ( (tmp & 1) == 1 ) {
						dp[i][j + 1] ++;
					}

				}
				// 2-2. '아' 
				else {
					// 오른 
					dp[i][j + 1] += (tmp / 2);

					// 아래
					dp[i + 1][j] += (tmp / 2);

					// 홀수면 아래로 한 번 더
					if ( (tmp & 1) == 1) {
						dp[i + 1][j] ++;
					}
				}
			}
		}



		// 3. N번째 경로 탐색 - dfs, bfs 방법 가능
		//     0 아래   /  1 오른
		int ansR, ansC; 
		ansR = ansC = 1;
		while (ansR <= H && ansC <= W) {

			// 3-1. ^XOR (다르면 1) 로 대체 가능 
			//       1) dp 방문횟수가 홀수 / map은 아래(0) 면 오른쪽 
			//       2) dp 방문횟수 짝수   / map은 오른(1) 면 오른
			if (  (dp[ansR][ansC] & 1) == 1 && map[ansR][ansC]==0  
				|| (dp[ansR][ansC] & 1) ==0 && map[ansR][ansC]==1 ) {
				ansC++;
			}
			// 3-2. 아래 경우의 수
			else {
				ansR++;
			}
		}
		
		// 4. 출력
		System.out.println(ansR+" "+ansC);
		br.close();
	}
}

 

C++ 코드 : 

// 산책 5573
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <algorithm>

#define MAX (1001+3)

using namespace std;

int H, W, N;	

int map[MAX][MAX];

// dp[i][j] : N-1번 산책했을때 {i,j}의 방문횟수
int dp[MAX][MAX];		

void input();

int main() {
	// 1. 입력
	//freopen("input.txt", "r", stdin);
	input(); 


	// 2. dp 배열 구하기
	// N-1번 산책할때 교차로를 몇번 지나게 되는지
	//     0 아래   /  1 오른
	dp[1][1] = N - 1;
	int tmp;
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			tmp = dp[i][j];

			// 2-1. 교차로에 '오'
			if (map[i][j] == 1) {
				// 오른쪽에 횟수 더해주기
				dp[i][j + 1] += (tmp / 2);

				// 아래에 횟수 더해주기 
				dp[i + 1][j] += (tmp / 2);

				// 방문횟수 홀수면 보정
				if (tmp & 1) {
					dp[i][j + 1] ++;
				}

			}
			// 2-2. '아' 
			else {
				// 오른 
				dp[i][j + 1] += (tmp / 2);

				// 아래
				dp[i + 1][j] += (tmp / 2);

				// 홀수면 아래로 한 번 더
				if (tmp & 1) {
					dp[i + 1][j] ++;
				}
			}
		}
	}



	// 3. N번째 경로 탐색 - dfs, bfs 방법 가능
	//     0 아래   /  1 오른
	int ansR, ansC; 
	ansR = ansC = 1;
	while (ansR <= H && ansC <= W) {

		// 3-1. ^XOR (다르면 1) 로 대체 가능 
		//       1) dp 방문횟수가 홀수 / map은 아래(0) 면 오른쪽 
		//       2) dp 방문횟수 짝수   / map은 오른(1) 면 오른
		if (  (dp[ansR][ansC] & 1) && map[ansR][ansC]==0  
			|| (dp[ansR][ansC] & 1) ==0 && map[ansR][ansC]==1 ) {
			ansC++;
		}
		// 3-2. 아래 경우의 수
		else {
			ansR++;
		}
	}

	printf("%d %d", ansR, ansC);

	return 0;
}

void input() {
	scanf("%d %d %d", &H, &W, &N);
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			scanf("%d", &map[i][j]);
		}
	}
}
#endif