[Algorithm] 백준 #4963 - 섬의 개수

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

4963번: 섬의 개수

 

📌 다시 봐야 할 부분

 

1. dx, dy를 모두 돌면서 확인해줄 때, 범위 벗어난 처리를 먼저!

if nx < 0 or nx >= w or ny < 0 or ny >= h:  # 범위를 벗어난 경우
    continue

이 부분을 먼저 적어주어야한다. 범위를 벗어난 경우의 처리를 아래로 빼주고 육지가 아닌 경우나 땅인 경우를 먼저 처리하려고 하면, out of index오류가 발생한다. 

 

 

주로 다른 bfs문제에서는 상하좌우만을 보면 되는데, 이 문제는 대각선으로 연결되었을때까지 확인해줘야 한다.

상하좌우 + 대각선 연결시 이동가능 -> 아래와 같이 총 8개로 잡아줘야한다

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

 

 

일반적인 상하좌우 문제에서는 dx, dy를 아래처럼 잡아준다.

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

 

2. 그리고 나의 삽질

 

맞게 푼 것 같은데 자꾸 index out of range가 발생해서 살펴보니, 행과 열의 확인 범위를 반대로 적어줬다.....ㅇㅏ..?

for i in range(h):
    for j in range(w):
        if graph[i][j] == 1:  #1(육지)이면
            result += 1
            bfs(i, j)

while문 안에서 i의 범위는 h이고, j의 범위는 w이므로, 

 

 

if nx < 0 or nx >= h or ny < 0 or ny >= w:  # 범위를 벗어난 경우

 

이게 맞는거다. h랑 w를 계속 반대로 적어줬다....

 

 

3. 방문처리

 

visited 배열을 만들어서 방문처리를 해주려고 했으나,

bfs함수로 확인을 하면서, 육지 방문시 방문된 것의 표시로 육지(1) -> 바다(0)로 바꿔주는 방법을 사용했다. 

 

 

📚 코드

import sys
from collections import deque

dx = [0, 0, 1, 1, 1, -1, -1, -1]  # 가로, 세로, 대각선 연결시 이동가능 -> 총 9개로 잡아줘야한다
dy = [-1, 1, -1, 0, 1, -1, 0, 1]


def bfs(x, y):  # 1이 땅, 0이 바다
    queue = deque()
    queue.append([x, y])

    while queue:
        x, y = queue.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= h or ny < 0 or ny >= w:  # 범위를 벗어난 경우
                continue
            if graph[nx][ny] == 0:  # 바다인경우 -> 계속하기
                continue
            if graph[nx][ny] == 1:  # 땅인경우
                graph[nx][ny] = 0  # visited를 사용하지 않고 방문한 땅은 0으로 바꿔준다!
                queue.append([nx, ny])  # 큐에 넣어주기

while True:
    w, h = map(int, sys.stdin.readline().rstrip().split())  # 너비, 높이
    if (w == 0) and (h == 0):
        break
    graph=[]
    for _ in range(h):
        graph.append(list(map(int, sys.stdin.readline().rstrip().split())))  # 지도 입력
    # visited = [[False] * w for _ in range(h)]
    result = 0
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1:  #1(육지)이면
                result += 1
                bfs(i, j)
    print(result)

 

 

 + dfs, bfs 두 방식으로 모두 푸는 것이 가능하다고 한다.

나는 bfs방식으로 풀어서 런타임에러(RecursionError) 가 나지 않았지만, dfs로 푼 경우 이를 위해

sys.setrecursionlimit(100000) 코드를 추가해줘야 한다. 

이유 : 파이썬의 재귀 깊이는 기본이 1000으로 설정되어 있는데, 이 문제의 제한에서는 깊이가 최대 2500까지 들어갈 수 있어 문제가 된다고 한다!! (w <= 50, h <=50 범위 확인!)