백준 9470 Strahler 순서 파이썬 풀이

난이도 : 골드3

풀이일 : 05077

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

9470번: Strahler 순서

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

오답 코드

import sys
from collections import deque

T = int(sys.stdin.readline().strip())
for _ in range(T):
    K, M, P = map(int, sys.stdin.readline().split())
    node = [0] * (M + 1)
    child = [[] for _ in range(M + 1)]
    count = [0] * (M + 1)
    temp = deque([] for _ in range(M + 1))
    for _ in range(P):
        a, b = map(int, sys.stdin.readline().split())
        child[a].append(b)
        count[b] += 1
    queue = deque()
    visited = [0] * (M + 1)
    for i in range(1, M+1):
        if not count[i]:
            visited[i] = 1
            queue.append(i)

    while queue:
        i = queue.popleft()
        for j in child[i]:
            count[j] -= 1
            temp[j].append(visited[i])
            visited[j] = max(visited[i], visited[j])
            if not count[j]:
                queue.append(j)
                if temp[j].count(max(temp[j])) > 1:
                    visited[j] = max(visited[i] + 1, visited[j])

    print(f'{K} {max(visited)}')

 

코드 구성

• child : 해당 노드 다음에 오는 노드 정보
• count : 해당 노드 전에 오는 노드 수
• temp : 해당 노드 이전 노드들의 Strahler
• 만약 temp[j] 번째 배열의 최대값 개수가 2개 이상이라면 visited[j] 값은 visited + 1, visited[j] 중 큰 값으로 재할당

틀린 이유

• 마지막 재할당 과정에서 앞선 노드의 visited 값이 다를 때, 마지막으로 호출된 i의 visited를 반영하게 되어 오답 발생

---

풀이 코드

import sys
from collections import deque

T = int(sys.stdin.readline().strip())
for _ in range(T):
    K, M, P = map(int, sys.stdin.readline().split())
    node = [0] * (M + 1)
    child = [[] for _ in range(M + 1)]    # 해당 노드 다음에 오는 노드
    count = [0] * (M + 1)                 # 해당 노드 전에 오는 노드 수
    temp = deque([] for _ in range(M + 1))    # visited[i] 저장
    for _ in range(P):    # 노드 방향, 수 조정
        a, b = map(int, sys.stdin.readline().split())
        child[a].append(b)
        count[b] += 1
        
    queue = deque()
    visited = [0] * (M + 1)
    for i in range(1, M+1):
        if not count[i]:    # 이전에 오는 노드가 없으면 queue 추가
            visited[i] = 1    # 처음 강줄기는 문제 조건에 따라 1 
            queue.append(i)

    while queue:
        i = queue.popleft()
        for j in child[i]:
            count[j] -= 1    # 호출 시 마다 앞서 오는 노드 줄이기
            temp[j].append(visited[i])    # 앞 강줄기 visited 저장
            visited[j] = max(visited[i], visited[j])    # 현재 visited 기록
            if not count[j]:    # 더이상 앞에 오는 강줄기가 없으면 queue 추가 
                queue.append(j)
                if temp[j].count(max(temp[j])) > 1:    # 최대값이 두 번 이상이면 +1 저장
                    visited[j] = max(temp[j]) + 1

    print(f'{K} {max(visited)}')    # 테스트케이스 번호와 바다에 닿는 값(최대값) 출력

코드 변화

• 마지막 재할당 과정에서 temp[j]의 최대값 + 1 재할당으로 수정 -> i 와 관계 없이 최대값을 재할당

---

느낀점

사람들이 많이 푼 문제를 풀어야겠다. 내게 맞는 반례를 구하기가 쉽지 않아서 한참 헤맸다.

또, 틀려서 계속 조금씩 바꾸면서 제출했더니 틀린 횟수만 엄청 늘어났다. 생각하고 확신이 있을 때 제출하자