[Baekjoon Online Judge] 백준 4963번 섬의 개수(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 4963번 섬의 개수

(Python)

(글쓴날 : 2020.03.29)

 

---

* Baekjoon Online Judge, 백준 4963번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 4963번 섬의 개수

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

---

2) 풀이 과정

1과 0이 저장되어 있는 2차원 배열이 주어지고 1을 땅, 0을 바다라 가정했을 때 땅들이 가로 세로 또는 대각선으로 연결되어 있는 섬의 개수를 출력하는 문제입니다.

 

저의 경우, BFS를 적용해 문제를 해결했으며, 2차원 배열을 완전 탐색하다 1이 발견되면 BFS를 통해 상하좌우와 대각선으로 연결되어 있는 땅들을 판별했습니다.

그 후, 총 BFS() 함수가 호출된 횟수로 섬의 개수를 구하여 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys, queue
input = sys.stdin.readline
 
 
def BFS(i, j):
    global w, h, MAP, visit, dx, dy, island
    island += 1
 
    q = queue.Queue()
    q.put((i, j))
 
    while q.qsize():
        x, y = q.get()
 
        if visit[x][y] == False:
            visit[x][y] = True
            for way in range(8):
                ii, jj = x + dx[way], y + dy[way]
 
                if ii < 0 or ii > h - 1 or jj < 0 or jj > w - 1:
                    continue
 
                if MAP[ii][jj] == 1:
                    q.put((ii, jj))
 
 
while True:
    w, h = map(int, input().split())
    if not w + h:
        exit()
    
    MAP = [list(map(int, input().split())) for _ in range(h)]
    visit = [[False] * w for _ in range(h)]
    dx, dy = [-1, -1, -1, 0, 0, 1, 1, 1], [-1, 0, 1, -1, 1, -1, 0, 1]
    island = 0
 
    for i in range(h):
        for j in range(w):
            if MAP[i][j] == 1 and visit[i][j] == False:
                BFS(i, j)
    
    print(island)

---