[BOJ_4963] 섬의 개수

 

이 문제는 DFS/BFS를 이용한 시뮬레이션 문제입니다. 좌표의 범위 내에서 육지의 지역을 순회하고 이동을 할 수 없으면 카운트를 올려주는 식으로 계산합니다. 말로 하면 간단한데 좌표에서 이동할 수 있는 경우(next position)를 모두 고려해야하므로 좌표의 정보를 구해줘야 합니다.

좌표 시뮬레이션 문제는 늘 그렇듯이

dx와 dy를 더해서 다음 좌표로 이동하기 때문에

dx = [-1,-1,-1,0,0,1,1,1]
dy = [-1,0,1,-1,1,-1,0,1]

를 준비합니다.

그리고 이 문제의 경우 다음 지도에서 섬의 개수가

5가 아닌 3인 것을 볼 때 상하좌우 뿐만 아니라 대각선까지 고려해 주어야한다는 것은 알 수 있습니다.

처음에는 DFS를 이용해서 여덟번의 재귀를 하는 식으로 구현했는데... IndexError가 나왔습니다.

그래서 BFS를 이용해서 다시 풀었습니다.

좌표를 큐에 넣어주는데 방문처리를 할 때 지도의 해당 좌표를 바다로 만들어 줍니다.

 

또 하나 실수한 것이 있는데요

deque을 사용할 때

queue = deque((x,y))

이런식으로 바로 튜플을 넣어서 사용할 경우

이런 모습으로 deque에 들어가게 됩니다. 이것은 우리가 의도한 것이 아니기 때문에

queue = deque()
queue.append((x,y))

튜플을 따로 append 해줘야 합니다.

기본 BFS 템플릿을 빠르게 상기해낸 후 지도의 범위내에서 움직이도록 만들어 주면 됩니다.

 

from collections import deque

result = []
dx = [-1,-1,-1,0,0,1,1,1]
dy = [-1,0,1,-1,1,-1,0,1]

def bfs(x, y):
    queue = deque()
    queue.append((x,y))
    graph[x][y] = 0
    while queue:
        now = queue.popleft()
        for i in range(8):
            nx = now[0] + dx[i]
            ny = now[1] + dy[i]
            if nx < h and nx >= 0 and ny < w and ny >= 0:
                if graph[nx][ny] == 1:
                    graph[nx][ny] = 0
                    queue.append((nx, ny))

while True:
    w, h = map(int,input().split())
    if w == h == 0:
        break

    count = 0
    graph = [list(map(int, input().split())) for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1:
                bfs(i,j)
                count+=1
    
    result.append(count)

for a in result:
    print(a)

 

www.acmicpc.net/problem/4963

4963번: 섬의 개수