[파이썬] 백준 22956 : 소나기 (골드1)

[파이썬] 백준 22956 : 소나기 (골드1)

• https://www.acmicpc.net/problem/22956

---

풀이

방향성 생각

• 일단 쉬운 유니온파인드 문제랑 다르게, 유니온만 진행하는게 아니라 다른 정보들도 전달해줘야한다.
• 일단 parent 배열을 1차원으로 축소해준다.
• parent에 x를 넣으면, 그 군집에 번호가 가장 작은 쪽으로 루트를 고정시켜준다. (일관된 기준만 있으면 달라도 상관 x)
• 이에 맞추어서 infos에 x의 부모인 px를 넣으면, 그 군집의 루트에 해당 지역에서 가장 낮은 높이, 비가 온 마지막 날짜, 루트의 위치를 저장한다.
• union + 정보전달이 필요한 문제

 

---

파이썬

import sys

input = lambda: sys.stdin.readline().strip()
inside = lambda x, y: 0 <= x < W and 0 <= y < H
dires = [(1,0),(0,1),(-1,0),(0,-1)]

H,W,K = map(int, input().split())

# 1. 개별 노드 관리: 높이
arr = [list(map(int,input().split())) for _ in range(H)]

# 2. 군집으로 관리: 날짜 / 깊이 / 위치 (위치 1차원 압축)
infos = [[0,1001,i] for i in range(H*W)]

P = [i for i in range(H*W)]
def find(x):
    if x != P[x]:
        P[x] = find(P[x])
    return P[x]

# 3. 쿼리 입력
for day in range(1,K+1):
    y,x,c = map(int,input().split())
    y -= 1
    x -= 1

    # 3-1. 해당 지점 높이 감소 -> 현재 연결된 군집 처리
    arr[y][x] -= c

    # 현재 좌표의 인덱스 변환 및 루트 찾기
    cur = x+y*W
    cur_p = find(cur)

    # 현재 좌표의 루트 정보 갱신
    if arr[y][x] < infos[cur_p][1]:
        infos[cur_p] = [day,arr[y][x],cur]
        P[cur_p] = cur_p

    # 3-2. 인접 지역 탐색 및 병합
    for dx,dy in dires:
        nx,ny = x+dx,y+dy
        if inside(nx,ny):
            nxt = nx+ny*W
            nxt_p = find(nxt)

            # 인접 지역에 비가 왔고 루트가 다르면 병합 진행
            if infos[nxt_p][0] and cur_p != nxt_p:

                # 항상 번호가 작은 쪽을 루트로 설정
                if cur_p > nxt_p:
                    cur_p,nxt_p = nxt_p,cur_p
                P[nxt_p] = cur_p

                # 군집 정보 갱신 (더 낮은 높이 -> 더 오래된 날짜 -> 더 작은 위치 순)
                cur_day,cur_depth,cur_loc = infos[cur_p]
                nxt_day,nxt_depth,nxt_loc = infos[nxt_p]

                if cur_depth < nxt_depth:
                    infos[cur_p] = [cur_day,cur_depth,cur_loc]
                elif nxt_depth < cur_depth:
                    infos[cur_p] = [nxt_day,nxt_depth,nxt_loc]
                else: 
                    # 깊이가 같다면 날짜와 위치비교
                    if nxt_day < cur_day or (nxt_day == cur_day and nxt_loc < cur_loc):
                        infos[cur_p] = [nxt_day, nxt_depth, nxt_loc]

    ay,ax = divmod(infos[find(cur)][2],W)
    print(ay+1,ax+1)

---

코멘트

• 어렵다기보단 union 연산 시 처리해야할 부분이 많아서 실수할 여지가 많았다...