[ BOJ 4963 ] 섬의 개수 (Python)

문제

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

문제를 잘 읽어야한다.
가로 + 세로 + 대각선 으로 연결되어 있는 사각형이 걸어갈 수 있는 곳이다.

문제를 대충 읽어서 가로 + 세로만 연결되어 있다고,,, 봤다 (삽질⛏)

문제 풀이

1. 바다가 아닌 땅(1)일 경우 그래프에 넣어준다.
   ➣ graph[(x,y)] = []
2. 만약 해당 땅의 가로,세로,대각선이 땅인 경우에 그래프의 value값으로 넣어준다.
   ➣ graph[(x,y)].append((nx,ny))
3. for문을 통해 그래프의 key 값을 dfs 함수로 넣어준다.
   ➣ for node in graph: cnt += dfs(node,0)
4. 방문하지 않은 곳이면, 방문했다고 체크해주고 value 값을 pop()해서 dfs에 한번 더 넣어준다.
   ➣ cnt += dfs((nx,ny),cnt)
5. 만약 방문한 곳이라면 연결된 섬이므로 return 0, 방문하지 않은 곳이라면 연결되지 않은 섬이므로 return 1을 해준다.
6. dfs의 return 값을 cnt 변수에 더해준다.

코드

import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline


def dfs(node,cnt):
    x, y = node[0], node[1]
    
    if visited[x][y] == 0:
        visited[x][y] = 1
        while graph[node]:
            next_node = graph[node].pop()
            nx, ny = next_node[0], next_node[1]
            
            cnt += dfs((nx,ny),cnt)
        return 1
    else:
        return 0

while (1):
    w, h = map(int,input().rstrip().rsplit())

    if w==0 and h==0 : break

    island, graph = [], {}
    visited = [[0] * w for _ in range(h)]
    cnt = 0
    # 하, 상, 좌, 우 , 상좌, 상우, 하좌, 하우
    dx = [1, -1, 0, 0, -1, -1, 1, 1]
    dy = [0, 0, -1, 1, -1, 1, -1, 1]

    for _ in range(h):
        row = input().rstrip()
        row = row.replace(' ','')
        island.append(row)

    for i,row in enumerate(island):
        for j,check in enumerate(row):
            if check == '1':
                graph[(i,j)] = []
                for k in range(8):
                    nx = i + dx[k]
                    ny = j + dy[k]
                    if 0 <= nx < h and 0 <= ny < w:
                        if island[nx][ny] == '1':
                            graph[(i,j)].append((nx,ny))

    for node in graph:
        cnt += dfs(node,0)

    print(cnt)