문제 풀이/백준
[Python] 백준 13565 : 침투
동까의 코딩
2024. 3. 30. 03:04
반응형
오늘의 문제인 침투를 풀어보았다.
기본적인 BFS & DFS로 풀 수 있었다.
https://www.acmicpc.net/problem/13565
13565번: 침투
첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않
www.acmicpc.net
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")
오늘도 감사합니다!
반응형