[Python] 백준 13565 : 침투

오늘의 문제인 침투를 풀어보았다.

기본적인 BFS & DFS로 풀 수 있었다.

 

https://www.acmicpc.net/problem/13565

13565번: 침투

 

dfs 풀이

import sys
sys.setrecursionlimit(3000000)

def dfs(y, x):
    per_lst[y][x] = 2
    for dy, dx in d:
        Y, X = y+dy, x + dx
        if (0 <= Y < M) and (0 <= X < N) and per_lst[Y][X] == 0:
            dfs(Y, X)

M, N = map(int, input().split())
per_lst = [list(map(int, list(input()))) for _ in range(M)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# print(per_lst)
for h in range(N):
    if per_lst[0][h] == 0:
        dfs(0, h)
print("YES" if 2 in per_lst[-1] else "NO")

 

 

 

bfs 풀이

import sys
from collections import deque
sys.setrecursionlimit(3000000)

def bfs(y, x):
    q = deque()
    q.append((y, x))
    per_lst[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 per_lst[Y][X] == 0:
                q.append((Y, X))
                per_lst[Y][X] = 2
                
                

M, N = map(int, input().split())
per_lst = [list(map(int, list(input()))) for _ in range(M)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# print(per_lst)
for h in range(N):
    if per_lst[0][h] == 0:
        bfs(0, h)
print("YES" if 2 in per_lst[-1] else "NO")

 

오늘도 감사합니다!