djgjdgjd   2년 전

아래 코드에서 좌표를 방문했을 때 3차원 배열을 놔서 벽을 부수지 않은 채 방문하면 visit_bfs[0][x][y], 벽을 부순 채 방문하면 visit_bfs[1][x][y] 이런식으로 구현 했습니다.

그런데 큐에 저장된 값들 중에 서로 다른 벽을 부순 상태에서 이동하다가 다른 벽을 부쉈을 때 이미 방문한 좌표랑 겹치면 그 좌표로 이동을 할 수 없으니 답이 틀려야 하지 않나요?

구조적으로 이해가 잘 안되네요 ㅠ 도움좀 주세여.. 

djm03178   2년 전

두 가지 부순 벽이 있을 때 이들을 각각 부수고 어떤 좌표에서 겹쳤다고 합시다. 만일 또다른 벽을 통과할 생각이 없다면 현재 상태가 어느쪽 벽을 부순 건지는 상관이 없습니다. BFS이기 때문에 최단 거리를 구하기만 하면 되거든요.

어느 쪽 벽을 부순 건지가 영향을 주려면 그 이후에 더 지나갈 수 있는 길에 제한이 생겨야 하는데, [1] 자체가 이미 벽을 더 부술 수 없다는 조건을 제시해주기 때문에 상관이 없습니다. 

chogahui05   2년 전

어디서부터 이해가 안 가시는지 잘 모르겠네요.

bfs를 한정적으로 생각하면 조금 어렵죠.. 잘 이해가 안 가고요.

가중치가 모두 같은 graph에서 AAA에서 BBB로 가는 최단거리를 찾는 게 bfs/dfs잖아요.


이 문제의 경우. 2가지가 중요한 변수입니다.

(1) 좌표

(2) 벽을 몇 번 부쉈는가?


bfs던 dfs던지 간에 상태들을 간선으로 연결한 graph를 가지고 탐색하는 게 핵심이에요.

만약에 벽이 없다면 상태 = (위치) 정도만 될 거고요.

벽을 부순다는 조건이 추가된다면 (벽을 부순 횟수, 위치) 정도가 추가되어야겠죠.

댓글을 작성하려면 로그인해야 합니다.