[Python] 백준, 2583(DFS)

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

2583번: 영역 구하기

* 골드 랭크로 승급하게 해 준 고마운 문항. 아직 그 정도 실력은 아닌 것 같지만 나름 뿌듯하다.

 

개요

- 자료구조가 조금 독특하다. 리스트를 어떻게 설정해야 하는지 고민을 조금 했는데, 구체적인 좌표는 그리 중요하지 않다는 걸 조금 늦게 깨달았다.

- 이제 dfs 알고리즘도 조금 익숙해진 것 같다. 함수의 틀은 문제별로 거의 고정인 것 같고, 응용하는 포인트들에서 차이가 나지 않나 싶다.

 

아이디어

- 변수 rec은 dfs 루프를 돌때마다 1씩 증가한다. for문을 돌면서 알아서 값이 초기화되도록 설정했고, global함수로 전역 변수로 설정해줬다.

- 변수 cnt는 영역의 개수를 나타내기 위한 변수인데, 결론적으로 len(result) 값과 일치해서 필요없는 변수였다.

- 마지막 줄의 *는 여러 값을 나타낼 때 쓰이는 값이다.

- x, y값의 순서가 정말 중요하다. 인덱스의 특성 때문인데, 일관되게 처리하는 게 중요하다.

 

# PYTHON CODE

import sys

sys.setrecursionlimit(10000)

a, b, c = map(int, sys.stdin.readline().split())
seq = [[0] * b for _ in range(a)]
result = []
cnt = 0

for _ in range(c):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
    for i in range(x1, x2):
        for j in range(y1, y2):
            seq[j][i] = 1


def dfs(x, y):
    global rec
    rec += 1
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    seq[y][x] = 1
    for k in range(4):
        nx, ny = x + dx[k], y + dy[k]
        if 0 <= nx < b and 0 <= ny < a and seq[ny][nx] == 0:
            dfs(nx, ny)


for i in range(a):
    for j in range(b):
        rec = 0
        if seq[i][j] == 0:
            dfs(j, i)
            cnt += 1
        if rec != 0:
            result.append(rec)

print(cnt)
result.sort()
print(*result)