[C++] 백준 7562번 나이트의 이동

그래프 탐색 문제.

나는 보통 배열을 쓸 때 1부터 쓰는 습관이 있는데, 이 습관이 이 문제에서는 정말 좋지 않게 작용했다.

초기화만 잘 해준다면 어렵지 않게 풀 수 있는 문제였다.

 

문제 풀이

문제가 대놓고 BFS (너비 우선 탐색)이라는 것을 말해주고 있다. 친절하게 그림으로도 나와있다.

각 테스트 케이스마다 좌표를 입력받고 BFS를 돌려가면서, 현재 몇 번째 탐색인지를 기록해나가며 최초로 발견한 곳에서의 번째 탐색을 찾으면 할 수 있다. 

바로 코드로 살펴보자.

 

사용한 STL과 변수

BFS를 하기 위해 queue STL을 사용했다.

• testCase : 입력받는 테스트 케이스의 개수이다.
• widthHeight : 각 테스트 케이스마다 입력받는 가로 세로의 길이이다.
• board 배열 : 해당 지점을 탐색했는지 flag를 세우기 위한 배열이다.
• curPoint, destPoint : 나이트의 현재 좌표와 목표하는 좌표를 {y, x}의 형태로 입력받는다.
• result : 총 몇번 움직여서 도달했는지 출력하기 위한 변수이다. 매 테스트 케이스마다 0으로 초기화 해주어야 한다.
• movePoint : 나이트가 이동할 수 있는 거리를 나타낸 것이다.

초기화 메서드

BFS 메서드

q가 이중 pair 자료형으로 되어있다. first에는 몇 번 탐색했는지, second에는 {y, x} 형태의 좌표가 들어있다.

처음에 입력으로 들어온 좌표를 탐색을 0번한 채로 큐에 넣어주고 BFSㄹ르 시작한다.

만일 현재 탐색중인 좌표가 목표하는 좌표와 같다면 탐색한 수를 result 변수에 저장한 후 BFS를 종료한다.

아니라면, 현재 나이트가 이동할 수 있는 좌표를 다음과 같은 조건이 아니라면 모두 큐에 넣어준다.

• 좌표의 범위가 음수이거나, 입력받는 길이보다 크거나 같을 때 (0부터 좌표가 시작하므로 입력받는 길이 - 1까지 가능하다.)
• 이미 해당 좌표를 탐색했을 때

메인함수

테스트 케이스를 입력받고 각 테스트 케이스마다 좌표를 입력받은 후,

BFS 탐색을 실시해주면 된다.

처음에 board 배열을 초기화 해줄때, 0부터 했어야했는데 1부터 초기화를 해서 틀렸었다.

또한, BFS 탐색시 최대길이를 포함하는 것도 틀린 원인 중 하나였다.

 

GitHub - kimyunseok/study-record: my study-record

코드 전문은 위에서 확인이 가능하다.