백준 알고리즘 13565번 침투(python)

기본적인 DFS & BFS 문제이다.

첫번째 줄만 탐색을 시킨 후에 마지막 줄이 탐색이 된 적 있으면 "YES" 아니면 "NO"를 출력해주면 된다.

DFS 풀이

import sys
sys.setrecursionlimit(3000000)

def dfs(y, x):
    graph[y][x] = 2
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < M) and (0 <= X < N) and graph[Y][X] == 0:
            dfs(Y, X)
            
M, N = map(int, input().split())
graph = [list(map(int, list(input()))) for _ in range(M)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for j in range(N):
    if graph[0][j] == 0:
        dfs(0, j)
print("YES" if 2 in graph[-1] else "NO")

BFS 풀이

from collections import deque
def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = 2
    while q:
        y, x = q.popleft()    
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < M) and (0 <= X < N) and graph[Y][X] == 0:
                q.append((Y, X))
                graph[Y][X] = 2
            
M, N = map(int, input().split())
graph = [list(map(int, list(input()))) for _ in range(M)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for j in range(N):
    if graph[0][j] == 0:
        bfs(0, j)
print("YES" if 2 in graph[-1] else "NO")