[BOJ 5573] 산책

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

5573번: 산책

 

- 문제 요약

 

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

상근이가 사는 마을

교차로에 쓰여 있는 문자가 오라면, 이 문자를 지우고 아를 쓴다. 그 다음에 오른쪽으로 진행한다. 만약, 교차로에 쓰여 있는 문자가 아라면, 이 문자를 지우고 오를 쓴 뒤, 아래로 진행한다. (입력이 들어올 때 0은 '아', 1은 '오'를 의미한다.)

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

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

 

 

- 알고리즘 정리

 

dp[i][j] : n-1번 동안 (i, j) 방문 횟수

 

교차로 방문 횟수가 홀수인지, 짝수인지를 따져서 경우에 따라 경로 탐색을 진행해 줍니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 1001
typedef long long ll;
int h,w,n,arr[MAX][MAX],dp[MAX][MAX];

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_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>h>>w>>n;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			cin>>arr[i][j];
		}
	}
	dp[1][1]=n-1;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			int w=dp[i][j];
			if(arr[i][j]==1){
				dp[i][j+1]+=(w/2);
				if(w%2==1){
					dp[i][j+1]++;
				}
				dp[i+1][j]+=(w/2);
			}
			else{
				dp[i][j+1]+=(w/2);
				dp[i+1][j]+=(w/2); 
				if(w%2==1){
					dp[i+1][j]++;
				}
			}
		}
	}
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(dp[i][j]%2==1){
				arr[i][j]++;
				arr[i][j]%=2;
			}	
		}
	}
	dfs(1,1);
}

코드 제출 결과