[Python] 백준 풀기 4963 - 섬의 개수

파이썬 백준 4963번

실버2

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

4963번: 섬의 개수

 

 

 

 

 

문제 보기

분류: 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

 

 

 

 

문제 풀기

기존 상하좌우 이웃으로 연결된 문제에서 대각선 네 방향에 대해 추가적 처리를 생각한다.

matrix 에서 처음으로 1을 발견하면 fnBFS() 를 실행하여 이웃된 8방향 모두 찾아가 1이 보이면 방문 처리한다.

이렇게 남은 matrix 에 대해 조건을 만족하여 fnBFS() 함수에 들어갈 때만 카운트를 세아려 총 섬의 개수를 구한다.

 

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline
from collections import deque

def fnBFS(a, b):
    dx = [-1, 1, 0, 0, -1, 1, -1, 1]
    dy = [0, 0, -1, 1, -1, -1, 1, 1]
    
    queue = deque([(a, b)])
    matrix[a][b] = 2            # 2로 방문 처리    
    
    while queue:
        x, y = queue.popleft()
        
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < h and 0 <= ny < w and matrix[nx][ny] == 1:
                matrix[nx][ny] = 2          # 2로 방문 처리
                queue.append([nx, ny])


if __name__ == "__main__":
    while True:
        w, h = map(int, inputdata().split())
        
        if (w, h) == (0, 0):
            break
        else:
            matrix = [list(map(int, inputdata().split())) for _ in range(h)]
            # print(matrix)           # test print
            
            count = 0
            for i in range(h):
                for j in range(w):
                    if matrix[i][j] == 1:           # 1로 시작하는 부분을 찾아 fnBFS 진입
                        fnBFS(i, j)
                        count += 1
            # print(matrix)           # test print
        print(count)

 

 

 

 

 

추가 하기

import sys
inputdata = sys.stdin.readline
from collections import deque

def fnBFS(a, b):
    dx = [-1, 1, 0, 0, -1, 1, -1, 1]
    dy = [0, 0, -1, 1, -1, -1, 1, 1]
    
    queue = deque([(a, b)])
    matrix[a][b] = 2            # 2로 방문 처리    
    
    while queue:
        x, y = queue.popleft()
        
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < h and 0 <= ny < w and matrix[nx][ny] == 1:
                matrix[nx][ny] = 2          # 2로 방문 처리
                queue.append([nx, ny])


if __name__ == "__main__":
    while True:
        w, h = map(int, inputdata().split())
        
        if (w, h) == (0, 0):
            break
        else:
            matrix = [list(map(int, inputdata().split())) for _ in range(h)]
            print(matrix)           # test print
            
            count = 0
            for i in range(h):
                for j in range(w):
                    if matrix[i][j] == 1:           # 1로 시작하는 부분을 찾아 fnBFS 진입
                        fnBFS(i, j)
                        count += 1
            print(matrix)           # test print
        print(count)



# 2 2
# 0 1
# 1 0
# [[0, 1], [1, 0]]
# [[0, 2], [2, 0]]
# 1

# 5 4
# 1 0 1 0 0
# 1 0 0 0 0
# 1 0 1 0 1
# 1 0 0 1 0
# [[1, 0, 1, 0, 0], [1, 0, 0, 0, 0], [1, 0, 1, 0, 1], [1, 0, 0, 1, 0]]
# [[2, 0, 2, 0, 0], [2, 0, 0, 0, 0], [2, 0, 2, 0, 2], [2, 0, 0, 2, 0]]
# 3

# 0 0