ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • BOJ 2178 DFS? BFS? DP?
    알고리즘 문제풀이/Java 2020. 5. 4. 23:27

     

     

    문제

     

    N×M크기의 배열로 표현되는 미로가 있다.

    1 0 1 1 1 1
    1 0 1 0 1 0
    1 0 1 0 1 1
    1 1 1 0 1 1

    미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

    위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

    입력

    첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

    출력

    첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착 위치로 이동할 수 있는 경우만 입력으로 주어진다.

    예제 입력 1 복사

    4 6 101111 101010 101011 111011

    예제 출력 1 복사

    15

    예제 입력 2 복사

    4 6 110110 110110 111111 111101

    예제 출력 2 복사

    9

    예제 입력 3 복사

    2 25 1011101110111011101110111 1110111011101110111011101

    예제 출력 3 복사

    38

    예제 입력 4 복사

    7 7 1011111 1110001 1000001 1000001 1000001 1000001 1111111

    예제 출력 4 복사

    13


    해설

     

    풀이는 다음과 같다. 

     

    DFS

    이 문제를 처음 풀었을 땐, DFS를 이용해서 풀었다. DFS와 BFS의 차이에 대해 깊게 생각해 본 적도 없고, 둘 다 그래프의 탐색의 방법이니 상관이 없을 것이라 생각했다.  

     

    계속 시간초과가 나는 걸 확인할 수 있었다. 

    DFS로 할 경우, 어느 한 지점에서 탐색할 수 있는 곳이 전에 지난 곳을 제외한 3곳이기 때문에 O(3^(w * h))의 시간 복잡도를 가지기 때문에 위와 같이 시간 초과가 나게 된다.

     

    DP

    두 번째로 생각한 풀이는 어느 한 지점에서 도착 지점까지 가는 방법의 최소값을 기록하는 DP형태의 풀이였다.

    도착 지점에서부터 시작해서 상하좌우를 탐색하면서 1씩 더하면 될 것 같은 느낌을 받았다. 하지만 막상 해보니 구현이 막막했다. 기존의 DP에선 최적 부분 구조를 파악하고, 작은 문제가 큰 문제를 해결할 수 있다는 걸 파악해야 하는데, 도저히 그러한 부분이 보이지 않았다.

    나중에 생각하고 알게 된 것이지만, 이제까지 풀었던 DP 문제의 경우, 어느 한 지점에서 오른쪽 혹은 아래로 가는 방법만 있는 그러한 조건이 있는 문제였기 때문에, 한 번 지나친 것에 대해 다른 값을 가질 일이 없었지만, 이 미로 탐색 문제의 경우, 상하좌우 모두 가능하며, 이 마저도 0은 못 가기 때문에 이미 지나친 곳이 다른 값을 가질 수 있다는 게 문제였다. 즉 점화식 형태로 표현할 수 없는 문제이기 때문에 DP를 통해선 해결할 수 없는 문제였다.

     

    BFS

    그렇게 고민하다가, 알고리즘 분류를 확인했는데, 이 문제의 경우 BFS라고 적혀있었다. 

    BFS로 할 경우, 시작 지점에서부터 깊이가 아닌 너비를 먼저 확인하고, 이후 도착 지점에 도착할 경우, 이 때의 깊이를 파악하면 되기 때문에 BFS로밖에 풀 수 없는 문제였다. 뿐만 아니라, 같은 깊이의 노드에 대해 탐색을 완료했다는 의미의 arrived [y][x] = true를 해주면, 어떤 칸 input [y][x]는 최소 깊이를 가질 때의 탐색만 처리하게 된다. 

    46번째 라인을 28번째로 옮길 경우, 직접 탐색할 때 도착 표시를 하기 때문에, 최소 깊이를 가질 때의 탐색만 하는 것이 아닌, 이후의 더 큰 깊이를 가질 때의 탐색도 하게 된다. -> 궁금하면 바꿔보고 디버깅을 통해 따라가보자. 메모리 초과가 날 것이다.

     

    즉, 이 문제의 경우 시작에서 도착까지의 깊이를 묻는 문제였고, 어떤 칸이 최소 깊이를 가질 때의 탐색을 묻는 것이기 때문에 BFS로 문제를 풀어야 한다. 

    느낀 점

    • BFS와 DFS를 문제를 풀 때, 고려하지 않았는데, 고려해야 함을 알게 해준 문제였다.

     

     

    댓글

Designed by Tistory.