백준 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번째 산책 경로 탐색을 해줍니다.