DFS/BFS의 선택 차이 - 최단 경로 풀기

백준 2178 

자연스럽게 DFS로 풀려헀으나 , 해당 문제는 DFS로는 풀 수 없는 문제였다 . 

 

import sys

import copy

N,M = map(int,sys.stdin.readline().split())

graph = []*(N)

for i in range(N) :

    graph.append(list(map(int,sys.stdin.readline().strip())))

# path = [ [False]*M for _ in range(N) ]

def DFS(x,y,cnt) :

   

    if x<0 or x>= N or y<0 or y>= M :

        return

   

    if (x == N-1) and (y == M-1) :

        cnt = cnt + 1

        return

    if copygraph[x][y] == 1 :

        copygraph[x][y] = 0

        cnt = cnt+1  

        DFS(x+1,y,cnt)

        DFS(x,y+1,cnt)

        DFS(x-1,y,cnt)

        DFS(x,y-1,cnt)

        return

    return

mincnt = 200

for i in range(N) :

    for j in range(M) :

        copygraph=copy.deepcopy(graph)

        cntglobal = 0

        DFS(i,j,cntglobal)

        if mincnt>cntglobal :

            mincnt= cntglobal

print(mincnt)

print(graph)

 

이렇게 해서 한번 방문할 때마다 돌아가는 형태로 풀려했으나, COPY와 초기화를 동시에 진행하기에는 문제가 있었고 그러므로 항상 0이 나왔다.

 그 이유는, 한번 지나가면 GRAPH를 0으로 변경해버리기 때문에 다시 지나지 않고, 그러므로 최단 거리를 찾기 힘들다.

(BFS도 , 다시 지나지 않게 풀지만 BFS는 한번 끝에 도달하면 그 경로가 최단의 거리이고

DFS는 처음 도달한 경로가 최단의 거리라는 보장이 없다) 

 

진행에 앞서, DFS와 BFS의 차이와 사용 경우를 비교해 보겠다. 

 

DFS : 

 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

이와 같은 문제를 해결할때 주로 푼다. 

CYCLE을 확인할때는 BFS로 확인하기 힘들다. DFS로 주로 사용한다. (BFS로도 가능은 하다)

아직 만나진 못했지만, 순열의 모든 조합을 확인할때는 DFS를 사용한다. 

(아마 순열이 저장되고, 순열은 TREE 구조에서 부모의 정보를 자식이 그대로 들고가기 때문인 것 같다. ) 

 

 

 

BFS : 

모든 노드 탐색에는 사용 가능하다. 

특히, 최소 거리 (DEPTH에 관련되었을때)는, BFS로 푼다!

DFS는 결국, 한곳을 끝까지 가고 모든 곳을 가는 것이기 때문에, 가장 짧은 DEPTH로 도달하는 경로를 찾으려면 모든 경로를 돌아야하고, 이는 시간초과를 유발하곤 한다. 

해당 개념을 주의하자. 

 

import sys

from collections import deque

N,M = map(int,sys.stdin.readline().split())

graph = []*(N)

for i in range(N) :

    graph.append(list(map(int,sys.stdin.readline().strip())))

dx = [-1,1,0,0]

dy = [0,0,-1,1]

def BFS(x,y) :

    q = deque()

    q.append([x,y])

    while q :

        arrar = q.popleft()

        x = arrar[0]

        y = arrar[1]

        for i in range(4):

            nx = x+dx[i]

            ny = y+dy[i]

            if 0 <= nx <N and 0 <= ny < M and graph[nx][ny] == 1 :

                q.append([nx,ny])

                graph[nx][ny] = graph[x][y] +1

                if nx == N-1 and ny == M-1 :

                    return graph[N-1][M-1]

print(BFS(0,0))

 

해당 코드 :

 

과정을 타협하기로 했다. 

1. nx ,ny는 arr로 구현하자. 

2. 구조를 보면, 어떻게 가든 간 depth가 결국 graph[nx][ny]이다. 

3. 그렇다면, 어떤 길로 가든 결국 depth 가 graph[n-1][m-1]에 저장된다. 

 

depth를 구성하면 된다! 

 

BFS면 도착한 DEPTH에 바로 종료한다.

DFS는 이미 지난 곳을 다시 지날 수 없고 모든 곳을 다 지나야 한다.

 

BREAK를 하지 않아도, 처음 도달한 NX-1 NY-1은 결국 그 점까지 도달하는 최소 값을 담고 있다.

(한번 도착한 곳은 되돌아 갈 수 없다 . )

즉 ,BFS는 최단 거리 문제에서 처음 도달하는 경로가, 무조건 최단 경로이다. 

 

최단 경로 문제는

BFS로 한번 도달한 곳은 다시 도달하지 않게 풀면, 그 경로가 최단 경로이다. 

 

**추가, GRAPH의 크기가 매우 크거나, (DEPTH가 멀다는 뜻이 아니다, DEPTH가 클 수 있으면 BFS가유리할 수 있다)한 경로의 정보를 저장해야한다면 DFS가 유리하다. (DFS는 한경로를 타고 가기 때문에 경로를 저장할 수 있다. 

 

 

dfs로 경로를 찾을땐, 한 경로를 찾고 나서는 돌아간 길을 check한것을 풀어주면 된다.