전공/백준
4963
yha97
2022. 11. 16. 11:41
날짜 : 2022. .
사용 언어 : python
문제
코드
import sys
from collections import deque
def bfs(a, b, idx):
queue.append([a, b])
earth[a][b] = idx
dx = [1, -1, 0, 0, 1, 1, -1, -1]
dy = [0, 0, 1, -1, 1, -1, 1, -1]
while queue:
temp = queue.popleft()
#print(temp)
for i in range(8):
x = temp[0] + dx[i]
y = temp[1] + dy[i]
if x in range(h) and y in range(w): # 범위에 있는 경우
if earth[x][y] == 1:
earth[x][y] = idx
queue.append([x, y])
return
while True:
w, h = map(int, sys.stdin.readline().split()) # 너비, 높이
if w == h and w == 0: break
earth = []
queue = deque()
cnt = 2
for _ in range(h):
earth.append(list(map(int, sys.stdin.readline().split()))) # 입력
for i in range(h):
for j in range(w):
if earth[i][j] == 1:
bfs(i, j, cnt)
cnt += 1
"""for i in earth:
print(i)"""
res = max(map(max, earth))
if res == 0: print(res)
else: print(res - 1)
풀이
- 평소에 풀어보았던 BFS 문제
- 다만 방향이 대각선까지 포함되었기 때문에 해당 케이스들을 이동방향을 저장하는 리스트에 넣어 저장 후 연산하는 것이 차이점이었다.
알게된 점
-
참고 사이트
-