[백준/파이썬] 27211 도넛 행성 쇼미더코드 3회차

#문제링크

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

27211번: 도넛 행성

#나의풀이

import sys

sys.stdin = open('../input.txt')

delta = [[-1, 0], [0, 1], [1, 0], [0, -1]]

def DFS(x, y):
    board[x][y] = 1
    for i in range(4):
        dx = x + delta[i][0]
        dy = y + delta[i][1]
        if dx < 0:
            dx += N
        if dx == N:
            dx = 0
        if dy < 0:
            dy += M
        if dy == M:
            dy = 0
        if board[dx][dy] == 0:
            DFS(dx,dy)

if __name__=="__main__":
    N, M = map(int, sys.stdin.readline().split())
    board = [list(map(int , sys.stdin.readline().split())) for _ in range(N)]
    count = 0

    for i in range(N):
        for j in range(M):
            if board[i][j] == 0:
                DFS(i,j)
                count += 1

    print(count)

#해설

DFS에서 기본이 되는 섬 찾기 문제에서 살짝 응용된 문제? 보자마자 풀었고 바로 통과해서 어려운점은 없었다.

    for i in range(N):
        for j in range(M):
            if board[i][j] == 0:
                DFS(i,j)
                count += 1

입력받은 배열에 0값을 찾고 DFS를 돌리게 된다 이 과정을 거치면 연결된 0들이 모두 1로 바뀌는 작업을 한다. 이후 섬의 개수를 늘려준다.

delta = [[-1, 0], [0, 1], [1, 0], [0, -1]]

def DFS(x, y):
    board[x][y] = 1
    for i in range(4):
        dx = x + delta[i][0]
        dy = y + delta[i][1]
        if dx < 0:
            dx += N
        if dx == N:
            dx = 0
        if dy < 0:
            dy += M
        if dy == M:
            dy = 0
        if board[dx][dy] == 0:
            DFS(dx,dy)

DFS의 값이 들어오면 현재 위치를 1로 바다로 바꿔주고 4방향 탐색을 하게 된다. delta 배열에 순서에 맞게 북동남서로 찾게되며 만약 0과 N범위를 벗어나면 잡아주는 작업을 한다. 나는 순수 노가다로 했는데 사실 벗어나는 경우 x부분은 N을 추가로 더해주고 %N으로 한 나머지 인덱스로 잡아줘도 될거 같았다. 이후 탐색한곳이 육지 즉 0이라면 다시 DFS에 값을 넣어준다.