[C++] 백준 2206번 벽 부수고 이동하기

그래프 탐색 문제.

최단 거리를 탐색하는 문제로, BFS를 응용해서 풀면된다.

조건을 따지지 못해서 검색을 했는데, 코드를 약간 수정해서 맞출 수 있었다.

 

처음에 이 문제를 접근했을 때

N x M의 맵이고, 벽은 1이고 땅은 0이다. 그리고 상, 하, 좌, 우를 이동할 수 있다.

1로 된 곳 중 하나를 부숴서 갈 수 있다.

나는 다음과같은 조건들을 고려했다.

• BFS로 점들을 이동하며, 내가 이 점에 왔을 때 벽을 부수고 온 것인지 아닌지를 고려했다.
• 만일 이전에 벽을 부수고 왔다면, 이번 정점에서는 벽을 가지 못하도록 했다.
• 이전에 벽을 부순적이 없다면, 벽을 부쉈다는 것을 기록하고 해당 벽을 방문한다.
• visit 2차원 배열을 만들어서 해당 지점을 방문한 것을 저장했다.

빨간색으로 칠한 이유는 저 부분을 다시 생각했어야 했기 때문이다.

이 문제를 약 한시간동안 고민하다가 결국 어디가 잘못된건지 못 찾아서 검색했다.

 

위에서 빨간색으로 색칠한 부분만 유의한다면 이 문제의 조건은 쉽게풀 수 있다.

• 해당 정점에 도착했을 때가 이전에 벽을 부수고 온 것인지, 벽을 부수지 않고 온 것인지를 나눠주고 방문기록을 저장한다.

위 조건이 이 문제의 핵심조건이다.

사실 이전에 벽을 부수고 왔다는 기록은 누구나 쉽게 생각할 수 있었을 것 같다. 나도 이 점까지는 고려해주었다.

그러나 경우를 나누어서 방문기록을 저장하지 못했었다.

 

글 읽기 - 반례 모음집

위 페이지를 가면, 맨 위에 중요한 반례가 하나 있다.

8 8 01000100 01010100 01010100 01010100 01010100 01010100 01010100 00010100 답 29

아마 나처럼 고려한 사람은 위 경우에서 -1이 나올것이다.

왜냐하면 이 케이스는 0으로 쭉 가다가 마지막 6번째 줄의 1에서 벽을 부수고 (8, 8)을 가는 것이 베스트이다.

 

하지만 벽을 부수지 않고 방문한 것과 벽을 부수고 방문한 것을 나누지 않고 고려하게되면

당장에 (1,3)의 0도 (1,1) -> (1,2) : 벽부숨 -> (1,3)의 거리로 방문이 되기 때문에

정답 케이스로 갈 수가 없어서 -1이 나오게된다.

 

처음에는 이 케이스를 맞추기 위해서 BFS를 수행하는 큐를 우선순위 큐로 만들어서 0이 있다면 0부터 수행하도록

만들었다. 그러나 이렇게하면 1일 때의 경우가 쌓이게되고, 만일 0일 때 마지막 정점을 방문하게 되면 마지막 정점이 방문처리가 돼서 벽을 부수고 가야 최단거리일 경우가 정답이 되지 못한다.

 

오답노트. 왜 오답인가?

결론은?

특정 정점에 도달했을 때, 벽을 이전에 부수고 도달했는지, 부수지 않고 도달했는지를 나눠서 방문을 기록한다.

 

내가 이전에 짰던 잘못된 코드를 봐보자.

나중에 보면 알겠지만 정답과 거의 유사하지만 정답이 되지 못한다.

다시 말하지만 정답 코드가 아니다. 왜 틀렸는지를 기록하는 중이고 정답 코드는 더 아래에 있다.

 

사용한 STL과 변수, BFS 탐색을 위한 NODE 클래스

• height, width : 높이와 너비이다.
• board : 판의 정보를 저장하는 배열
• visit : 해당 정점을 방문했는지를 기록
• check : 마지막 M, N을 방문했는지 저장하기 위한 변수.
• result : 결과값. 최단경로를 출력한다.
• direction pair 자료형 배열 : 상, 하, 좌, 우를 이동하기 위해 더해주는 배열
• Node 클래스 : 정점의 좌표와 해당 정점까지 왔을 때의 거리, 그리고 이전에 벽을 부쉈는지 기록하는 alreadyCrash 변수가 있다.

bfs 메서드 - 1

시작점은 항상 1, 1이고 해당 정점을 포함하므로 시작 거리를 1로 만든다.

벽은 부순적이 없으므로 최초에는 false로 만들고, Node 자료형 큐를 만든다.

그리고 큐를 사용해서 BFS를 수행한다. 노드의 변수를 쉽게 사용하도록 변수 4개를 만들어서 사용한다.

 

여기서 잘못된 점 하나가 있다.

• M, N의 정점에 도달하면 BFS를 종료한다.

사실 M, N의 정점에 도달하는 방법은 위에서 말했다시피 벽을 안 부수고 갈수도, 벽을 부수고 갈수도있기 때문에 이렇게 고려하면 안된다.

 

bfs 메서드 - 2

그리고 상, 하, 좌, 우 방향에 따라 BFS를 진행해준다.

현재 좌표에서 방향을 더해준 값이 올바르고, 해당 정점을 방문하지 않았다면,

1. 해당 정점이 0, 즉 그냥 갈 수 있다면 Q에 넣고 방문처리 해준다.
2. 해당 정점이 1, 벽을 부수고 가야한다면, 내가 만약 벽을 부수고 온 상태라면 큐에 넣지 않고 벽을 부수지 않고 왔다면 벽을 부쉈다고 기록해주고 큐에 넣어준다.

메인함수

처음에 높이와 너비를 입력받고, 문자열 형태의 input을 입력받는다.

숫자들의 입력이 붙어있으므로, 문자열 형태로 입력받아서 배열에 저장시켜준다.

 

그리고 bfs() 메서드를 돌려서

1. check가 true, 즉 마지막 점을 방문했다면 갱신된 결과값을 출력한다.
2. check가 false라면 마지막 점을 방문하지 못했다는 뜻이므로 -1을 출력한다.

 

이 코드는 11%에서 틀렸습니다. 가 나온다.

이유는 위에서 말했다시피 방문기록을 벽을 부숴서 간 것과 부수지 않고 간 것으로 나누어야 하기 때문이다.

 

문제풀이

이제 정답 코드를 살펴보자. 오답이 된 위 코드에서 수정된 것이 많이 없다.

사용한 STL과 변수

변수는 큰 차이가 없다.

result 값을 10억으로 초기화 시켜서, 최초로 갱신되는 최단거리는 무조건 갱신되도록 만들었다.

그리고 visit 배열이 3차원으로 변했다.

이는 좌표를 나타내는 이차원 배열의 각 원소에

• 벽을 부수고 도달했는지, visit[i][j][1]
• 벽을 부수지 않고 도달했는지, visit[i][j][0]

를 기록하기 위해 추가되었다.

 

나머지는 위와 동일하다.

 

bfs 메서드 - 1

bfs 메서드도 시작 부분에 visit 배열을 true로 만들때, 시작점은 벽을 부수지 않았으므로 0으로 해놓고 방문기록을 저장한다.

그리고 큐가 비지 않을 때까지 bfs()를 실행한다.

현재 정점이 M, N 정점이라면 result 값의 도착하는데 걸린 거리를 저장해준다.

만일 벽을 부수고 도착한 경우와 벽을 부수지 않고 도착하는 경우 두 가지 경우가 있을 수 있으므로,

최소값으로 갱신되도록 해준다.

 

bfs 메서드 - 2

뒤에 부분 역시 동일하지만, visit 배열을 쓰는 것만 다르다.

현재 벽을 부쉈는지, 안부쉈는지에 따라 visit배열을 사용하고, 0일때와 1일때를 나누어서 큐에 집어넣고 방문기록을 저장한다.

 

메인함수

메인함수는 위와 같은 메커니즘이다. 설명을 생략하도록 하겠다.

 

조금만 더 생각했다면 풀 수 있었을까? 하는 아쉬움이 남는 문제다.

그래프 탐색 문제는 자신이 있었어서 풀 수 있을거라고 생각했는데,

이런 그래프 탐색 문제도 있구나 라는 것을 알게됐다.

 

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

코드는 위에서 확인 가능하다.