[0208 TIL]HUFS 겨울방학 코테대비 캠프(dfs, bfs)

DFS, BFS에 대한 고찰

드디어 깨우쳐 버린 그래프 탐색. 재귀 함수에 대한 것을 이해하고 보니 dfs가 쉬워졌다. 리스트로 푸는 문제는 전에 이해가 가능했었는데 그래프에서는 어려움을 겪었었다. 근데 알아버림

 

두, 네 방향 탈출 가능 여부 판별 DFS와 BFS차이

| 문제

n * m 크기의 이차원 영역의 좌측 상단에서 출발하여 우측 하단까지 뱀에게 물리지 않고 탈출하려고 합니다. 이동을 할 때에는 반드시 상, 우에 인접한 칸으로만 이동할 수 있으며, 뱀이 있는 칸으로는 이동을 할 수 없습니다. 예를 들어 <그림 1>과 같이 뱀이 배치 되어 있는 경우 실선과 같은 경로로 탈출을 할 수 있습니다. 이 때 뱀에게 물리지 않고 탈출 가능한 경로가 있는지 여부를 판별하는 코드를 작성해보세요.

DFS(두방향)

n , m = tuple(map(int, input().split()))
grid = [
    list(map(int, input().split()))
    for _ in range(n)
]

visited = [
    [0 for _ in range(m)]
    for _ in range(n)
]

def in_range(x, y):
    return 0 <= x < n and 0 <= y < m

def can_go(x, y):
    if not in_range(x, y):
        return False
    
    if visited[x][y] == 1 or grid[x][y] == 0:
        return False
    
    return True

dxs, dys = [0, 1], [1, 0]

def dfs(x, y):
    for dx, dy in zip(dxs, dys):
        nx, ny = x + dx, y + dy
        
        if can_go(nx, ny):
            visited[nx][ny] = 1
            dfs(nx, ny)
        

visited[0][0] = 1
dfs(0, 0)

print(visited[n - 1][m - 1])

• 처음에 visit에 처음 점을 넣고, 방문했다는 것을 체크한다.
• 그리고 dfs로 접근
• dx, dy로 검사해주고 다음 칸이 갈 수 있을 때, visited를 1로해주고 다시 dfs로 들어간다.

BFS(네 방향)

from collections import deque

n, m = tuple(map(int, input().split()))
grid = [
    list(map(int, input().split()))
    for _ in range(n)
]

visited = [
    [0 for _ in range(m)]
    for _ in range(n)
]
def in_range(x, y):
    return 0 <= x < n and 0 <= y <m

def can_go(x, y):
    if not in_range(x, y):
        return False
    
    if grid[x][y] == 0 or visited[x][y]:
        return False
    
    return True

q = deque()

dxs, dys = [1, -1, 0, 0], [0, 0, -1, 1]

def bfs():
    while q:
        x, y = q.popleft()
        for dx, dy in zip(dxs, dys):
            nx, ny = x + dx, y + dy
            if can_go(nx, ny):
                q.append((nx, ny))
                visited[nx][ny] = 1
                         
q.append((0, 0))
visited[0][0] = 1
bfs()
print(visited[n - 1][m - 1])

 

• bfs는 처음 0, 0을 q에 넣고, 방문했다는 것을 체크한 뒤, bfs에 들어간다.
• q가 다 빌 때까지 큐에서 다음 대상인 x, y를 pop해주고
• dx, dy로 nx, ny를 뱉고, 갈 수 있는지 검사.
• 갈 수 있으면 q에 넣어두고 visited 체크

다른 문제들도 풀어보면서 더 익혀야겠다.