<내 코드>
from collections import deque
def bfs(x, y):
direction = [(1, 0), (-1, 0), (0, 1), (0, -1),
(1, 1), (1, -1), (-1, 1), (-1, -1)]
queue = deque() #탐색을 하려는 좌표를 담는다.
queue.append((x, y))
maps[x][y] = 0
while queue:
now = queue.popleft()
for i in range(8): #상하좌우 대각선까지 탐색
nx = now[0] + direction[i][0]
ny = now[1] + direction[i][1]
if(0 <= nx < h) and (0 <= ny < w):
if maps[nx][ny] == 1:
maps[nx][ny] = 0
queue.append((nx, ny))
while True:
w, h = map(int, input().split())
maps = []
cnt = 0
if w == 0 and h == 0:
break
for _ in range(h):
tmp = list(map(int, input().split()))
maps.append(tmp)
for i in range(h):
for j in range(w):
if maps[i][j] != 0:
cnt += 1
bfs(i, j)
print(cnt)
1. w, h, 지도를 입력받는다.
2. 매 입력마다 BFS 탐색을 마치면 cnt를 +1 해준다.
3. BFS를 상하좌우 그리고 대각선까지 여덟 방향을 다 탐색한다.
4. 탐색 중 지도에서 1인 값을 0으로 바꾸고 큐에 좌표를 넣고 탐색을 반복한다.
반응형
'알고리즘 문제풀기 > 백준 - Python' 카테고리의 다른 글
[백준 2667] 단지번호 붙이기 - Python (그래프, BFS) (0) | 2020.09.01 |
---|---|
[백준 7576] 토마토 - Python (그래프, BFS) (0) | 2020.09.01 |
[백준 2583] 영역 구하기 - Python (그래프, BFS) (0) | 2020.08.31 |
[백준 1012] 유기농 배추 - Python (그래프, DFS) (0) | 2020.08.31 |
[백준 11724] 연결 요소의 개수 - Python (그래프탐색, DFS) (0) | 2020.08.31 |