[BOJ]4963 - 섬의 개수 (Python)

문제 

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

코드 

from collections import deque
import sys
input = lambda : sys.stdin.readline().strip()


def bfs(x, y):
    queue = deque([(x, y)])
    visited[x][y] = 1
    while queue:
        cx, cy = queue.popleft()
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0), (-1, 1), (1, -1), (1, 1), (-1, -1)]:
            nx, ny = cx + dx, cy + dy
            if nx < 0 or nx > h-1 or ny < 0 or ny > w-1 :
                continue
            if visited[nx][ny] == 0 and graph[nx][ny] == 1:
                queue.append((nx, ny))
                visited[nx][ny] = 1


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

    # 종료 조건
    if w == 0 and h == 0:
        break

    graph = [[0] * w for _ in range(h)]
    visited = [[0] * w for _ in range(h)]
    count = 0

    for i in range(h):
        graph[i] = list(map(int, input().split()))

    for i in range(h):
        for j in range(w):
            if visited[i][j] == 0 and graph[i][j] == 1:
                bfs(i, j)
                count += 1

    print(count)

 

풀이 

처음으로 좌표를 사용해서 푼 문제이다. 어떻게 풀어야 하는지 갈피를 못잡고 있었는데 옆에 있던 사람이 도와줘서 풀 수 있었다. 

 

• [(0, 1), (0, -1), (1, 0), (-1, 0), (-1, 1), (1, -1), (1, 1), (-1, -1)]를 활용해서 현재 위치에서 내가 갈 수 있는 8개의 자리를 확인한다 
• 범위 밖으로 나가지 않고 방문한 적 없고, 갈 수 있는 길이면 큐에 넣고 다시 bfs를 돌린다 
• 벡터 좌표 사용하는 방법만 익히면 풀 수 있는 문제였다