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

문제 링크

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

카테고리

BFS, 아이디어

문제 풀이

1. BFS 탐색을 통해 원숭이가 도착점에 도달하는지 판단한다.

 

2. 이를 위해 방문 배열을 설정한다.

    2.1 boardVisit[x][y][move] : (x,y) 지점에 move만큼 이동횟수가 남은 채로 온 적이 있다.

 

3. 12가지 경우의 수를 이용해 원숭이의 다음 위치를 계산해 큐에 넣는다.

    3.1 (0~3 : 상하좌우, 4~11 말처럼 이동) - dx[12], dy[12]
    3.2 남은 이동 횟수가 0이라면 말처럼 이동하지 않는다.
    3.3 만약에 방문한 곳이 해당 이동 횟수를 통해 이미 방문한 곳이 아닐때만 큐에 넣어준다.

 

4. 도착점에 도달하면 현재 이동한 횟수를 출력한다.

5. 큐가 빌 동안 도달하지 못한다면 -1을 출력한다.

 

주의할 점

* 방문 배열 처리 때문에 애먹었던 문제이다. 단순히 다시 방문하지 않게만 처리 하면 틀린다.

  (이렇게 하면 경우의 수가 달라진다.)

* H가 행이고 W가 열이다.

코드 (C++)

채점 결과

한마디

  쉬운 문제만 풀다 보니까 방문 배열 처리를 너무 간단하게 처리하는 버릇이 생긴 것 같다.

  여러 유형의 문제들을 풀어 보면서 좀 더 꼼꼼하게 푸는 습관을 만들어야 겠다. 😲