[알고리즘] 백준 2178번

[알고리즘] 백준 2178번

문제

https://www.acmicpc.net/problem/2178

---

풀이

알고리즘 공부를 하면서 자료구조도 간간히 복습하고 있습니다. 그리고 최근에 복습한 것이 바로 BFS와 DFS 알고리즘입니다. 단순히 자료구조를 공부하기 위해 구현을 하는 것은 그렇게 어렵지 않았고 실제 알고리즘에서 어떻게 활용될지가 궁금해 BFS 알고리즘 하나를 시도해봤습니다. 하지만 기본 BFS 알고리즘 조차 문제로써 나오니 쉽게 떠오르지 않는 부분도 있었고 새로 알게 된 점도 있었습니다. 다음은 저의 풀이과정입니다.

1. DFS로 시도하였으나 최소의 칸 수이기 때문에 DFS로는 조금 까다로울 것 같아서 BFS를 선택했습니다.
2. BFS로 어떻게 최소의 칸수를 구할까 고민하던 중 지금 문제는 최소 경로가 아닌 최소의 칸수라는 것을 알았습니다. 최소 경로와 최소의 칸수는 같은듯 다른 의미를 갖습니다. 여기서 최소의 칸수는 BFS의 레벨이며 이 레벨을 통해 특정 지점까지 도달하는 최소의 칸수를 알 수 있습니다.

코드는 다음과 같습니다.

1. 저는 현재 점을 기준으로 오른쪽, 위, 왼쪽, 아래 순서로 돌며 검사를 하고 큐에 넣어주었습니다.
2. 사실 저에게 가장 복병같은 존재였습니다. 방문을 표시해주는 코드는 원래 for뮨 바로 위에 있었습니다. 하지만 그대로 코드를 제출하니 시간초과가 나오더라구요. 그리고 질문 게시판을 찾아보니 이렇게 하면 같은 점에 대해 중복검사를 시행할 수 있다는 답변을 보았습니다. 그리고 생각해보니 실제로 같은 점이 두번 큐에 두번 들어가게 되더라구요. 예를 들어 2X2 배열에 모두 1을 넣고 (0,0)부터 시작한다고 생각을 해보세요. 처음 큐에. (1,0)과 (0.1)이 들어가고 각각 주변 유효 점에 대한 검사를 할 때 모두 (1,1)을 큐에 넣어주게 됩니다. 그렇기 때문에 (1,1)에 대해 중복 검사가 일어나게 됩니다. 그렇기 때문에 큐에 들어갈 점은 반드시 방문을 하게 되니 큐에 넣을 때 방문을 했다고 처리하면 이후에 큐에 중복해서 들어갈 일은 없습니다.
3. 유효 검사(좌표의 유효 범위, 길이 맞는지, 이미 방문을 했는지)를 통과한 점을 큐에 넣습니다.
4. 2번과 같이 이 문제에서 가장 중요한 부분입니다. BFS의 레벨이 곧 최소의 칸수인데 레벨 별로 어떻게 구분을 해야하나 고민을 했습니다. 레벨은 결국 이전 레벨의 +1이므로 큐에 들어가는 점이 다음 레벨의 점이고 현재 점이 현재 레벨이기 때문에 다음과 같은 코드를 작성하였습니다.