[BOJ] 4963번 섬의 개수 / 사용언어 : 파이썬(python)

※ 문제링크 

4963번: 섬의 개수

해당 문제는 BFS를 사용해서 해결할 수 있는 문제였다. 문제에서 상,하,좌,우 뿐만아니라 대각선까지도 이동가능하다는 점만 신경써서 코드를 작성하면 비교적 간단하게 해결할 수 있어서 해당방식으로 코드를 작성하였다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력값을 바탕으로 2차원 배열로 지도형태를 구현한다.

2. 이어져 있는 섬들을 탐색할 수 있는 BFS함수를 작성한다.(방문한 섬의 경우 2로 변경하여 방문여부를 표기했다.)

3. 배열의 크기만큼 반복문으로 탐색을 하면서 방문하지 않은 섬이 나올 때마다 BFS함수를 실행하고 cnt에 +1을 해준다.

4. 지도의 모든 좌표를 탐색한 후 결과값을 출력한다.

+ 해당문제는 종료조건을 입력받기 전까지 계속 실행해야하는 것을 유의하여 코드를 짜야한다.

+ 입력값이 많아 sys함수로 입력값을 받았다. sys함수 사용시에는 개행문자에 유의하자

 

from collections import deque
import sys

while True:
    # input = sys.stdin.readline
    w, h = map(int, input().split()) # w: x좌표 / h: y좌표
    if w == 0 and h == 0:
        break
    field = []
    for _ in range(h):
        field.append(list(map(int, input().split())))

    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])
        field[y][x] = 2
        
        while queue:
            x, y = queue.popleft()
            for i in range(8):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < w and 0 <= ny < h and field[ny][nx] == 1:
                    field[ny][nx] = 2
                    queue.append([nx, ny]) 

    cnt = 0
    for x in range(w):
        for y in range(h):
            if field[y][x] == 1:
                bfs(x, y)
                cnt += 1
    print(cnt)

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.