3. 이코테 - DFS BFS - 미로 탈출 (BFS 핵심)

다 필요없고 BFS 핵심

0. BFS는 재귀 X이다.
1. 따라서 BFS 안에 큐 생성한다
2. 시작 포인트 일단 넣는다

3. while queue
4.    현위치 = popleft()
5.    for 다음위치(또는 다음 노드) 가져와
6.        다음 위치가 조건에 맞으면(또는 방문 안했으면) 이동시켜
7.        queue.append(다음위치)   <--- 개중요 (for안에 넣어서 다음위치/이웃노드 전부 넣어주는)

• 그리고 DFS 문제든 BFS 문제든 방문 기록을 활용하는 방식으로,
• "방문 기록"을 남기는 방향으로 문제를 푸는 유형이다 라고 생각하면 될거같다.

---

---

• 링크 : https://www.youtube.com/watch?v=7C9RgOcvkvo

---

• 내가 잘못 푼 경우인데, 이 경우 DFS가 되어서
• 잘 가다가 상하좌우가 전부 1일 때 내가 dx, dy 설정을 한 순서대로 타고 내려감
  • 뭔 소리냐면, [좌, 하, 우, 상] 으로 설정했기 때문에
    
    여기서 4열 맨 오른쪽에서 '하'로 안가고, DFS라서 '좌'로 계속 타고 내려감
    => 정답이 안됨

''' 내가 풀다 만 - 잘못된 풀이 (실패작) '''
def dfs(n, m, y, x, graph, cnt):
    graph[y][x] = 0    # visit처리
    
    #    좌 하 우 상
    dy = [0, 1, 0, -1]
    dx = [-1, 0, 1, 0]
        
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        
        if ny == n and nx == m:
            break
        
        if 0 <= ny and ny < n and 0 <= nx and nx < m:
            if graph[ny][nx] == 1:
                cnt += 1
                cnt = dfs(n, m, ny, nx, graph, cnt)
        
    return cnt    
    
    
def sol(n, m, graph):
    cnt = 0
        
    cnt = dfs(n, m, 0, 0, graph, cnt)
    
    cnt += 2  # 시작노드와 끝노드 더해줌
    return cnt


n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
print(sol(n, m, graph))

---

---

동빈나 솔루션 정리

• (1,1)부터 BFS를 활용하여 최단 거리를 기록하면 해답을 얻을 수 있다!

''' 다시 풀어보자 => BFS로 가야해, BFS가 핵심이야! DFS하면 안돼! '''
# BFS는 회귀가 아니고 while - for를 사용한다

from collections import deque

def BFS(y, x, graph):
    
    queue = deque()
    queue.append((x, y))               # (중요) 1. BFS는 맨첨에 방문할걸 일단 넣는다 -> 큐에
        
    #    좌 하 우 상
    dy = [0, 1, 0, -1]
    dx = [-1, 0, 1, 0]
    
    while queue:
        x, y = queue.popleft()        # (중요) 2. BFS는 일단 뺀다 (= 얘의 이웃 가자)
        ''' [현 위치에서의 BFS 수행] '''
        for i in range(4):
            # (중요) 3. 이웃 계산 = 다음 이동할 위치 계산
            ny = y + dy[i]
            nx = x + dx[i]
            
            # 범위 밖으로 나갈 경우 -> 무시
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue

            # 이동 후 0일 경우 -> 무시
            if graph[nx][ny] == 0:
                continue

            # 이동 후 1일 경우 -> 이전거 + 1
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))             # (개중요) 4. 이동 했으면 이동한 놈을 넣는다
    
    # BFS 전체를 끝내버린 후 그래프 마지막 위치의 값만 리턴하면 됨
    return graph[n-1][m-1]
    
print(BFS(0, 0, [[1, 0, 1, 0, 1, 0],
 [1, 1, 1, 1, 1, 1],
 [0, 0, 0, 0, 0, 1],
 [1, 1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1, 1]]))

---

---

실행결과 보기 - BFS로 진행해야 한다

''' 다시 풀어보자 => BFS로 가야해, BFS가 핵심이야! DFS하면 안돼! '''
# BFS는 회귀가 아니고 while - for를 사용한다

from collections import deque

def BFS(y, x, graph):
    
    queue = deque()
    queue.append((x, y))               # (중요) 1. BFS는 맨첨에 방문할걸 일단 넣는다 -> 큐에
        
    #    좌 하 우 상
    dy = [0, 1, 0, -1]
    dx = [-1, 0, 1, 0]
    
    while queue:
        print(graph[0])
        print(graph[1])
        print(graph[2])
        print(graph[3])
        print(graph[4])
        print('------------------')
        
        x, y = queue.popleft()        # (중요) 2. BFS는 일단 뺀다 (= 얘의 이웃 가자)
        ''' [현 위치에서의 BFS 수행] '''
        for i in range(4):
            # (중요) 3. 이웃 계산 = 다음 이동할 위치 계산
            ny = y + dy[i]
            nx = x + dx[i]
            
            # 범위 밖으로 나갈 경우 -> 무시
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue

            # 이동 후 0일 경우 -> 무시
            if graph[nx][ny] == 0:
                continue

            # 이동 후 1일 경우 -> 이전거 + 1
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))             # (개중요) 4. 이동 했으면 이동한 놈을 넣는다
    
    # BFS 전체를 끝내버린 후 그래프 마지막 위치의 값만 리턴하면 됨
    return graph[n-1][m-1]
    
print(BFS(0, 0, [[1, 0, 1, 0, 1, 0],
 [1, 1, 1, 1, 1, 1],
 [0, 0, 0, 0, 0, 1],
 [1, 1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1, 1]]))

• 이런 느낌임 (참고로 여기서 끝난게 아니고 아래처럼 끝까지 가긴 함)
  • 그래서 마지막까지 loop 끝나면 return graph[n-1][m-1] 을 해주는 것
    

아무튼 핵심

0. BFS는 재귀 X이다.
1. 따라서 BFS 안에 큐 생성한다
2. 시작 포인트 일단 넣는다

3. while queue
4.    현위치 = popleft()
5.    for 다음위치(또는 다음 노드) 가져와
6.        다음 위치가 조건에 맞으면(또는 방문 안했으면) 이동시켜
7.        queue.append(다음위치)   <--- 개중요 (for안에 넣어서 다음위치/이웃노드 전부 넣어주는)