https://www.acmicpc.net/problem/4963
휴가 직전은 항상 번아웃이 오는 것 같다. 번아웃이라는 단어로 삶을 대체하기엔 그리 치열하게 살지는 않았던 것 같아서 부끄럽지만, 사람은 핑계의 산물 아니겠는가. 어쨌든 여러 핑계를 뒤로하고 오늘부터 다시 1일 1 알고리즘 체재로 포스팅하지 않을까 싶다.
익숙한 BFS/DFS 문항들은 이제 가닥만 조금 잡히면 구현하는 데에 있어서는 크게 문제 되지 않는 거 같다.
# PYTHON CODE (1) - DFS
import sys
sys.setrecursionlimit(100000)
dx = [-1, 1, 0, 0, -1, 1, -1, 1]
dy = [0, 0, -1, 1, 1, -1, -1, 1]
def dfs(x, y):
for n in range(8):
nx = dx[n] + x
ny = dy[n] + y
if 0 <= nx < b and 0 <= ny < a and tree[nx][ny] == 1:
tree[nx][ny] = 0
dfs(nx, ny)
while True:
cnt = 0
a, b = map(int, sys.stdin.readline().split())
if a == 0 and b == 0:
break
tree = [list(map(int, sys.stdin.readline().split())) for _ in range(b)]
for i in range(b):
for j in range(a):
if tree[i][j] == 1:
tree[i][j] = 0
dfs(i, j)
cnt += 1
print(cnt)
간단한데, 기존의 경우와는 다르게 대각선으로 걸쳐있는 방향도 고려해줘야 해서 경우의 수를 4가지 늘려줬다. 그 외의 부분은 유사하다.
첫 제출 때, 재귀 애러가 발생해서 sys모듈의 recursionlimit()매서드를 사용하였다. 기본값으로 설정되어 있는 재귀 참조의 범위를 인위적으로 늘려주는 함수다.
# PYTHON CODE (2) - BFS
import sys
from collections import deque
dx = [-1, 1, 0, 0, -1, 1, -1, 1]
dy = [0, 0, -1, 1, 1, -1, -1, 1]
def bfs(x, y):
queue = deque()
queue.append([x, y])
while queue:
x1, y1 = queue.popleft()
for n in range(8):
nx = dx[n] + x1
ny = dy[n] + y1
if 0 <= nx < b and 0 <= ny < a and tree[nx][ny] == 1:
tree[nx][ny] = 0
queue.append([nx, ny])
while True:
cnt = 0
a, b = map(int, sys.stdin.readline().split())
if a == 0 and b == 0:
break
tree = [list(map(int, sys.stdin.readline().split())) for _ in range(b)]
for i in range(b):
for j in range(a):
if tree[i][j] == 1:
tree[i][j] = 0
bfs(i, j)
cnt += 1
print(cnt)
간만에 풀어서 queue의 존재를 잊기는 했는데, 마찬가지로 구현 자체는 무리 없이 패스.
'백준 > BFS (너비 우선 탐색)' 카테고리의 다른 글
[Python] 백준, 1697(BFS) (0) | 2021.09.10 |
---|---|
[Python] 백준, 7576(BFS) (0) | 2021.09.09 |
[Python] 백준, 1012(DFS/BFS) (0) | 2021.09.09 |
[Python] 백준, 2606(DFS/BFS) (0) | 2021.09.08 |
[Python] 백준, 2667(BFS/DFS) (0) | 2021.09.06 |