백준 - 공주님을 구해라

문제 출처: https://www.acmicpc.net/problem/17836

17836번: 공주님을 구해라!

 

3차원 배열을 통해 검을 먹었을 때와 아닐 때를 구분해야 한다.

최단시간이고 N, M, T의 범위가 크므로 BFS탐색을 선택.

 

매번 이동할 때마다 검을 가지고 있는지 없는지를 확인

1. 다음 좌표가 벽인 경우
   1. 검을 가지고 있는 경우 → 3차원 배열 체크 후 이동
   2. 검을 가지고 있지 않는 경우 → 이동 불가
2. 다음 좌표가 길(==0) 일 경우
   1. 방문 체크하고 Queue에 넣는다.
3. 다음 좌표가 '그람'일 경우(==2)
   1. wall을 1로 해주고, 방문체크 및 Queue에 넣는다.

 

클래스에서는 r, c, isSword, wall 이렇게 4개의 변수를 갖는다.

좌표가 2인 곳에 도착하면 isSword는 true가 되고 벽을 한번 부수고 지나가면 false로 변환.

벽을 부수면 wall이 1 아니면 0

 

→위와 같은 방식으로 진행할 경우 문제 지시에 어긋난다.(필자가 문제를 제대로 파악.. 아니 읽기 못했다..)

 

위의 실수를 깨닫고 그러면 간단히 전역 변수로 하면 해결되지 않을까??라고 생각했다.

 

 

위 사진처럼 isSword 변수를 두고 2인 지점에 도달하면 false였던 값을 true로 변환해주었다. 하지만 이것 또한 잘못된 판단이었다..

 

만약 한 곳에서 먼저 그람을 만나 벽을 뚫을 수 있게 된다면, 아직 그람에 도달하지 못한(곧 도달할) 좌표에서는 그람에 도달하지 않고도 벽을 뚫는 것이 가능해진다.