[baekjoon] 백준 1780번(파이썬): 종이의 개수

문제

1780번: 종이의 개수

알고리즘

- 반복문을 통해 종이를 확인한다.

- 시작점에 종이의 수가 현재 종이의 수와 다르다면 3* 3 범위를 재귀적으로 탐색한다.

- 탐색할 때 3으로 나눈 범위를 그 종이의 수 x, y 좌표를 탐색한다.

- 탐색이 모두 끝난 구역은 카운트한다.

코드

import sys


def dfs(x, y, z):
    global answer
    visited = graph[x][y]

    # 반복문을 통해 종이를 확인
    for i in range(x, x + z):
        for j in range(y, y + z):
            # 시작점에 종이의 수가 현재 종이의 수와 다르다면
            if graph[i][j] != visited:
                # 3 * 3 범위를 재귀적으로 탐색
                for k in range(3):
                    for l in range(3):
                        dfs(x + k * z // 3, y + l * z // 3, z // 3)
                return

    # 카운트
    if visited == -1:
        answer[0] += 1
    elif visited == 0:
        answer[1] += 1
    else:
        answer[2] += 1


n = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
answer = [0, 0, 0]
dfs(0, 0, n)
[print(res) for res in answer]

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법