[Python] 27211. 도넛 행성

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

27211번: 도넛 행성

 

 

접근법

• N X M map을 순회하면서 0(빈공간)을 찾음.
• 찾게 된다면 해당 위치에서 상하좌우가 이동할 수 있는 공간인지 확인.
  -> 이동할 수 있다면 하나의 공간이라 취급하고, 방문했다는 의미로 map의 값을 1로 변환
  -> 이동할 수 없다면 continue

def input_func(N, M):
    arr = [[[] for _ in range(M)] for _ in range(N)]
    for i in range(N):
        arr[i] = list(map(int,input().split()))
    return arr

def solution(map, N, M):
    ans = 0
    dir_list = [[1,0], [-1,0], [0,1], [0, -1]]

    for i in range(N):
        for j in range(M):
            if not map[i][j]: # 빈 공간일 때만 listed에 넣어 주위 탐방
                ans += 1
                listed = [[i,j]]
                while listed:
                    x, y = listed.pop()
                    for a,b in dir_list:
                    	# N 혹은 M을 넘어가면 처음으로 돌아가야하기 때문에 모듈러 연산 사용
                        new_x = (x + a) % N
                        new_y = (y + b) % M

                        if not map[new_x][new_y]: # 0 (빈공간)이라면
                            listed.append([new_x,new_y])
                            map[new_x][new_y] = 1
    print(ans)

def main():
    N, M = map(int, input().split())
    map_list = input_func(N, M)
    solution(map_list, N, M)

if __name__ == '__main__':
    main()

---

사용된 알고리즘

그래프 이론, 그래프 탐색, 너비 우선 탐색