https://www.acmicpc.net/problem/4963
4963번: 섬의 개수
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 일반적인 상, 하, 좌, 우 네가지 방향을 탐색하는 bfs 문제에서 조금 벗어난 대각선까지 포함하는 8가지 방향을 탐색해야 하는 문제 입니다.
일반적인 네가지 방향의 경우와 달리 여덟가지 방향을 그림으로 표현하면 다음과 같습니다.
따라서 dx, dy 리스트를 다음과 같이 만들고 for i in range(8)로 반복하면 됩니다.
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
from collections import deque
def bfs(graph, visited, i, j):
q = deque()
q.append((i, j))
visited[i][j] = 1
while q:
x, y = q.popleft()
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
if graph[nx][ny] == 1 and visited[nx][ny] == 0:
visited[nx][ny] = 1
q.append((nx, ny))
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]
while True:
m, n = map(int, input().split())
if m == 0 and n == 0:
break
graph = []
for _ in range(n):
graph.append(list(map(int, input().split())))
visited = [[0] * m for _ in range(n)]
count = 0
for i in range(n):
for j in range(m):
if graph[i][j] == 1 and visited[i][j] == 0:
bfs(graph, visited, i, j)
count += 1
print(count)
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 7569번: 토마토(Python) (0) | 2022.01.15 |
|---|---|
| 백준 알고리즘 10026번: 적록색약(Python) (0) | 2022.01.15 |
| 백준 알고리즘 18870번: 좌표 압축(Python) (0) | 2022.01.14 |
| 백준 알고리즘 7576번: 토마토(Python) (0) | 2022.01.14 |
| 백준 알고리즘 18870번: 좌표 압축(Python) (0) | 2022.01.12 |