백준 2644 촌수계산 파이썬 풀이, 반례

난이도 : 실버2
풀이일 : 04123
 
https://www.acmicpc.net/problem/2644

2644번: 촌수계산

---

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

---

1차 시도 오답

import sys

def find(num, l):
    queue = []
    queue.append(num)
    while queue:
        k = queue.pop(0)
        if parent[k]:
            l.append(parent[k])
            queue.append(parent[k])
    return

m = int(sys.stdin.readline().strip())
t1, t2 = list(map(int, sys.stdin.readline().split()))
r1, r2 = [0], [0]
n = int(sys.stdin.readline().strip())

parent = [0] * (m+1)
left = [0] * (m+1)
right = [0] * (m+1)
for i in range(n):
    p, c = list(map(int, sys.stdin.readline().split()))
    if left[p]:
        right[p] = c
    else:
        left[p] = c
    parent[c] = p

find(t1, r1)
find(t2, r2)

result = -1
for i in range(len(r1)):
    for j in range(len(r2)):
        if r1[i] and r1[i] == r2[j]:
            result = i + j

print(result)

코드 구성
1. 각 인풋으로 부모와 왼쪽 자식, 오른쪽 자식 리스트 채우기
2. 주어진 두 타겟 숫자의 개별 조상 찾기 함수 실행
3. 공통 조상의 겹치는 숫자를 찾아 인덱스의 합 출력
 
틀린 이유
1. 한 타겟이 다른 타겟의 부모일 때 문제 발생
2. 공통 조상이 겹치는 경우, 더 많은 촌수를 출력

---

2차 시도 오답

import sys

# 두 타겟의 부모-자식 관계 판별 함수 추가
def find(n1, n2):
    if parent[n1] == n2 or parent[n2] == n1:
        print(1)
        return
    listup(t1, r1)
    listup(t2, r2)
    final()
    return

# 타겟별 조상 리스트업 함수
def listup(num, l):
    queue = []
    queue.append(num)
    while queue:
        k = queue.pop(0)
        if parent[k]:
            l.append(parent[k])
            queue.append(parent[k])
    return

# 최종 결과 출력 함수 추가
def final():
    result = -1
    for i in range(len(r1)):
        for j in range(len(r2)):
            if r1[i] and r1[i] == r2[j]:
                result = i + j + 2

    print(result)
    return

m = int(sys.stdin.readline().strip())
t1, t2 = list(map(int, sys.stdin.readline().split()))
r1, r2 = [], []
n = int(sys.stdin.readline().strip())

parent = [0] * (m+1)
left = [0] * (m+1)
right = [0] * (m+1)
for _ in range(n):
    p, c = list(map(int, sys.stdin.readline().split()))
    if left[p]:
        right[p] = c
    else:
        left[p] = c
    parent[c] = p

find(t1, t2)

코드 변화
1. 두 타겟 숫자의 부모-자식 요소 판별을 위한 함수 추가
2. 최종 결과 출력 함수 추가로 공통 조상 중 작은 것을 기준으로 둠
 
틀린 이유
1. 조상 정보만 기록하여 일부 반례에서 문제 발생
2. 자식이 둘 이상인 경우 문제 발생

---

최종 정답

import sys

# 타겟 숫자 개별 조상 찾기
def listup(num, l):
    queue = []
    queue.append(num)
    while queue:
        k = queue.pop(0)
        for q in range(1, m + 1):
            if family[q][k] == 1:
                l.append(q)
                queue.append(q)
    return

# 최종 반환 함수
def final(r1, r2):
    for i in range(len(r1)):
        for j in range(len(r2)):
            if r1[i] == r2[j]:
                return print(i + j)
    return print(-1)

m = int(sys.stdin.readline().strip())
family = [[0] * (m + 1) for _ in range(m + 1)]
t1, t2 = list(map(int, sys.stdin.readline().split()))
# 조상 리스트 첫 요소로 본인 추가
r1, r2 = [t1], [t2]
n = int(sys.stdin.readline().strip())

# 부모-자식 관계 2차원 배열
for _ in range(n):
    p, c = list(map(int, sys.stdin.readline().split()))
    family[p][c] = 1

listup(t1, r1)
listup(t2, r2)
final(r1, r2)

코드 변화
1. 조상 리스트 첫 인자 0 -> 타겟 숫자로 수정
-> 첫 요소로 타겟 숫자를 직접 집어 넣어 일부 반례에서 발생하던 문제 해결
 
2. 부모-자식 판별 함수 삭제
-> 1 수정에 의해 자연스럽게 이후 비교 과정에서 비교할 수 있게 됨
 
3. 부모-자식 정보 2차원 배열 저장
-> 자식을 둘 이상 가지는 경우에서 발생하던 문제 해결

---

반례

입력	3 1 2 2 3 1 3 2	4 1 2 3 1 2 2 3 3 4	5 3 4 4 2 3 3 4 1 2 4 5	10 7 6 9 1 2 1 3 1 4 9 1 9 10 3 5 3 6 2 7 2 8	12 7 6 11 1 2 1 3 2 7 2 8 2 9 4 5 4 6 8 10 10 11 11 12 12 4
정답	2	1	1	4	7

너무 겹치는 것들은 제외하고 다섯 가지 반례 기록

---

느낀점
확실히 꾸준히 문제를 풀 때보다 로직을 생각해내고, 코드를 수정 하는 데에 어려움이 느껴진다.
정확한 로직을 짜기보다는 우선 얼렁뚱땅 구현하고 이후 수정하는 코딩을 하는 것 같아 나쁜 습관이 들기 전에 바로잡아야겠다.