[백준] 20364_부동산 다툼 (Python) - 다시 풀기

20364_부동산 다툼 (Python)

0. 출처

• 유형 : 트리 (silver 2)
• 링크 : 20364번: 부동산 다툼

1. 기록

• 22/04/18 (월)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 땅의 갯수는 노드의 갯수이다. 6개이므로 7개 공간의 이차원 리스트를 만들자.
>> 이때 트리의 모양은 이진트리이다.
>> 이진트리처럼 만들어주려면 어떻게 해야할까? [[], [2,3],[4,5],[6]]
>> 오리의 번호 대로 방문표시를 해놓자.
>> 오리가 자기 번호로 가는길에 방문 표시를 한 땅을 밟은 경우 땅의 번호를 리턴하자.
>> 무사히 자기 땅에 간 경우는 0을 리턴하자.

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
6 4 (땅의 갯수 / 오리의 수)
3 (오리가 가지고 싶어하는 땅의 번호)
5
6
2

- 예제 출력 1 -
0
0
3
0

(3) 코드

# 틀린 코드
# 디버깅용

from copy import deepcopy

n = int(6)
m = int(4)

num = n
temp = 0

tree = [[], [2, 3], [4, 5], [6]]
land_list = [3, 5, 6 ,2]

print(tree)

visited = deepcopy(tree)

def travel(start, land, flag, answer_list):
    if len(tree) > start:
        for index in range(len(tree[start])):
            if flag == False:
                return

            if tree[start][index] == land:
                visited[start][index] = 0
                flag = False
                answer_list.append(0)
                return flag

            elif tree[start][index] != land:
                if visited[start][index] == 0:
                    flag = False
                    answer_list.append(tree[start][index])
                    return flag
                elif visited[start][index] != 0:
                    next = tree[start][index]
                    flag = travel(next, land, flag, answer_list)
                    if flag == False:
                        return
    else:
        return

answer_list = []

print(land_list)

for land in land_list:
    flag = True

    travel(1, land, flag, answer_list)
    print(answer_list)

print(answer_list)

(4) 정리

로직을 아예 잘못짰다.
전체를 방문하다보니 방문한 곳의 자식노드가 내가 찾는 land 인지 아닌지를 구분해놓지 않아서
이미 방문한 곳이 visited = 0 인 경우 바로 해당 land를 반환하도록 짜버려서 답이 엉뚱하게 나왔다.
다시풀어보자.

(5) 참고

참고 풀이