[백준 1600] 말이 되고픈 원숭이 (C++)

A. 문제설명

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

문제에 대한 자세한 설명은 링크 참조

 

1. H*W 크기의 배열이 주어짐

2. 원숭이는 0,0의 위치에서 H,W의 위치로 이동하고자 함

3. 원숭이는 기본적으로 상하좌우 인접한 칸으로 이동이 가능하나 아래와 같은 말의 이동을 따라하려 함

	x		x
x				x
		말
x				x
	x		x

4. 말의 이동동선은 다음과 같은데, 원숭이는 해당 이동을 K번 따라할 수 있음

5. 말의 이동방법과 원숭이의 이동방법을 동원하여 목적지로 최소의 이동으로 이동하고자 함

6. 그 최소의 이동횟수를 구하고 못구하면 -1 반환

 

B. 접근법

BFS

 

기본적으로 BFS로 간단하게 풀 수 있는 문제이다. 원숭이가 K번 말의 이동을 모사할 수 있는 경우를 고려하여 구조체를 다음과 같이 구현하였다. 여기서 k는 말 이동 횟수를 계수하여 K번이 넘지 않게 확인하기 위함이다.

typedef struct{
  int x, y, d, k; // x,y:원숭이 좌표, d:이동 횟수, k:말 이동 횟수
} MONKEY;

 

여기서 주의해야 할 점이 방문여부를 체크하는 visit 배열 사용시, 말이동 횟수인 k도 고려하여야 하는데, 처음에 visit을 visit[201][201]으로 구현한 결과 테스트를 통과하지 못했다.

visit[201][201][31]로 바꾸고 통과할 수 있었는데, k번째의 말이동을 하고 다음 위치로 탐사하는 경우의 경로와 k+n번째의 말이동을 하고 다음 위치로 탐사하는 경우의 경로가 달라질 수 있기 때문이다. 따라서 이를 고려하여 visit 배열을 구현해야 한다.

 

C. 풀이

1. BFS는 처음 상의 위치에서 탐사를 시작

2. K번의 말 이동 횟수를 못 채웠을 경우 8방향의 말 이동방향 탐사

3. 4방향의 일반 방향탐사는 기본적으로 다 탐사

4. 탐사 visit 배열에 체크 후 큐에 삽입

5. 목적지 도달시, 해당 최단 이동횟수 반환

6. 큐가 빌때까지 탐사해도 목적지 도달 불가능시 -1 반환

 

D. 내 코드