백준 5573번 산책

< 백준 5573번 산책 - 마포 코딩박 >

사용한 알고리즘: DP


 HxW 인 grid 가 주어지고, 각 교차점에는 '오' , '아' 둘 중 하나가 써있습니다. 문제에서 주어지는 규칙에 따라 산책을 진행할 때, N번째 산책에서 산책이 종료되는 교차로를 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (기본 생각)
  N-1번의 산책으로 각 교차로가 각각 몇번씩 방문되는지 본다는 것입니다.
 N-1번의 산책동안 (x,y) 교차로가 홀수번 방문됐다면 N번째 산책시 (x,y) 교차로의 글자가 바뀌어 있을 것이고 ('오'->'아' 혹은 '아'->'오'), 짝수번 방문됐다면 초기 글자가 그대로 쓰여있을 것입니다.

(2) (코드 6~8)
 'dp[x][y] : N-1번의 산책동안 (x,y) 교차로 방문 횟수' 라고 설정했습니다.

(3) (코드 25~47)
 당연하게도 dp[1][1] = N-1 입니다. 이를 기준으로 모든 교차로의 방문횟수를 정해줍니다.

(4) (코드 48~59)
 각 교차로 방문 횟수이가 홀수인지, 짝수인지 판단하여 각 교차로의 '오', '아' 를 결정해줍니다.

(5) (코드 8~17, 60~61)
 바뀐 산책로를 따라 N번째 산책 경로 탐색을 해줍니다.

	#include <iostream>
	using namespace std;
	// 오른쪽 or 아래쪽으로만 움직인다!
	// 칸마다 밟은 횟수 dp 로 계산!
	int H, W, N, arr[1111][1111];
	// dp[x][y]: (x,y) 교차로를 지나간 횟수
	int dp[1111][1111];
	// N번째 산책을 따라가 봅시다!
	void DFS(int x, int y){
	// 종료되는 교차로
	if(x>H||y>W){
	cout << x << ' ' << y << '\n';
	return;
	}
	if(arr[x][y]==0) DFS(x+1,y);
	else DFS(x,y+1);
	}
	int main(){ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
	// 0: 아래쪽 , 1: 오른쪽
	cin >> H >> W >> N;
	for(int i=1; i<=H; ++i)
	for(int j=1; j<=W; ++j)
	cin >> arr[i][j];
	// N-1번 산책할 때 각 교차로가 몇번 지나게 되는지
	dp[1][1] = N-1;
	for(int i=1; i<=H; ++i){
	for(int j=1; j<=W; ++j){
	int Value = dp[i][j];
	// (i,j) 교차로에 '오'라고 써있을 때
	if(arr[i][j]==1){
	// 자신의 오른쪽
	dp[i][j+1] += (Value/2);
	if(Value%2==1) dp[i][j+1] ++;
	// 자신의 아래쪽
	dp[i+1][j] += (Value/2);
	}
	// '아' 라고 써있을 때
	else{
	// 자신의 오른쪽
	dp[i][j+1] += (Value/2);
	// 자신의 왼쪽
	dp[i+1][j] += (Value/2);
	if(Value%2==1) dp[i+1][j] ++;
	}
	}
	}
	//교차로의 N번째 방향
	//dp값 mod 2 -> 0이면 초기 방향 그대로, 1이면 바뀜
	for(int i=1; i<=H; ++i){
	for(int j=1; j<=W; ++j){
	// 방향이 바뀌어야 하는경우 (홀수번 방문)
	if(dp[i][j]%2==1){
	//초기값에 +1 해주고 mod 2 (방향전환)
	arr[i][j]++;
	arr[i][j]%=2;
	}
	}
	}
	// N번째 경로탐색
	DFS(1,1);
	return 0;
	}

view raw BOJ 5573.cpp hosted with ❤ by GitHub