섬의 개수(백준 4963번)

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

해당 문제는 기본적인 그래프 탐색을 적용하면 풀 수 있는 문제이다.

BFS 알고리즘을 사용해서 문제를 풀었는데, 일반적인 문제가 방향벡터가 동서남북 4가지만 존재하는 반면, 해당 문제는 나이트의 이동처럼 특정 좌표에서 대각선을 탐색하는 벡터가 추가적으로 필요하다.

 

최종적인 방향 벡터는 다음과 같다.

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

각각 하, 우, 상, 좌, 왼쪽 위 대각선, 오른쪽 위 대각선, 왼쪽 아래 대각선, 오른쪽 아래 대각선을 체크하는 방향벡터이다.

 

이후 2차원 행렬을 2중 for문을 돌면서 방문해주는데, bfs() 메서드를 사용해서 방문체크를 진행해주면서 카운트를 올려준다. 각 bfs 호출에서 방문했던 좌표를 visited 처리하기 떄문에, 방문된 좌표는 for문에서 걸러지게 되고 문제를 해결할 수 있다.

 

다음은 전체 코드이다.

import sys
from collections import deque

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

def bfs(x, y):
    q = deque()
    q.append((x, y))
    
    while q:
        cx, cy = q.popleft()
        for dir in range(8):
            nx = cx + dx[dir]
            ny = cy + dy[dir]
            if 0 <= nx < h and 0 <= ny < w and not visited[nx][ny]:
                if matrix[nx][ny] == 1:
                    visited[nx][ny] = True
                    q.append((nx, ny))

while True:
    w, h  = map(int, sys.stdin.readline().split())
    if w == 0 and h == 0: break
    matrix = [ list(map(int, sys.stdin.readline().split())) for _ in range(h) ]
    visited = [[False for _ in range(w)] for _ in range(h)]
    cnt = 0
    for i in range(h):
        for j in range(w):
            if not visited[i][j] and matrix[i][j] == 1:
                cnt += 1 
                visited[i][j] = True
                bfs(i, j)
    print(cnt)