[백준 알고리즘] 백준 3182번 한동이는 공부가 하기 싫어! 파이썬(Python)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 3182번 한동이는 공부가 하기 싫어! 파이썬(Python)

1) 문제번호 : 3182번

 

2) 문제 출처

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

3182번: 한동이는 공부가 하기 싫어!

 

2. 문제

H-ALGO 회원인 한동이는 공부하는것을 좋아하지 않는다. 하지만 약삭빠르게도 한동이는 공부도 하지 않으면서 어려운 시험을 통과하고 싶어한다.

그러던 와중 어느 날, 한동이의 동기가 한동이에게 선배들 중 누군가가 시험의 답을 알고있다는 꿀정보를 알려주었다. 하지만 안타깝게도 그 정보는 사실이 아니어서 선배들조차도 정답은 알지 못하고 다른 누군가가 알고 있을거 같다는 정보만 알고 있는 것이었다.

한동이는 택민이에게 시험 정답을 물어보았다. 택민이는 답을 모른다고 했지만 택민이는 상준이가 답을 알고 있을 것 같다고 하였다. 그 후, 한동이는 상준이에게 물어보고 그리고...

어느 순간 한동이는 아무리 이걸 해도 자신에게 도움이 되지 않는것을 깨닫고 굉장히 슬퍼졌다. 하지만 그는 이걸 함으로써 많은 선배들과 인맥을 쌓을 수 있고, 이게 언젠가 큰 도움이 될 것이라는 것을 깨달았다!

당신의 목표는 한동이가 한 사람에게만 시험문제를 물어볼 수 있다고 할 때, 최대한 많은 선배들을 만날 수 있게 하기 위해서 누구에게 시험문제를 물어 볼 것인지를 알려주는 것이다.

 

3. 제약사항

4. 입력

입력의 첫 줄에는 정수 N이 주어진다. N은 2이상 1000 이하의 자연수이다. 선배들은 1부터 N까지 번호지어져 있다.

다음 N줄에 하나의 숫자가 주어진다. 첫 번째 줄은 첫 번째 선배의 대답이고 두 번째 줄은 두 번째 선배의 대답이다. 이렇게 N번째 선배의 대답까지 입력이 주어진다.

 

5. 출력

첫째 줄에 한동이가 물어봐야 할 선배의 번호를 출력한다. 하나 이상의 정답이 있다면 번호가 작은 선배를 출력한다. 

 

6. 풀이

- 간단한 DFS 문제다.

- 처음 선배의 대답부터 DFS 를 도는데, 방문자의 수를 체크하고, DFS를 끝낸 다음에는 누가 방문자 수가 더 큰지에 대해 who를 계속 갱신해주면 된다.

 

7. 소스 코드

import sys
input=sys.stdin.readline

N = int(input()) # 선배의 수

# 선배의 대답
help = [0,]

# 입력
for _ in range(N) :
    help.append(int(input()))

# DFS
def DFS(start, cnt) :
    # 방문
    visit[start] = True

    # 방문한 수
    cnt += 1

    # 입력값이 0이 아니고 방문하지 않았다면 DFS 돌자
    if help[help[start]] != 0 and visit[help[start]] == False :
        cnt = DFS(help[start], cnt)
    return cnt

who = 0 # 누구를 먼저 만나야 하니

# 방문 수
maxCount = 0

for i in range(1, N+1) :
    # 방문 확인 배열
    visit = [False for _ in range(N+1)]

    #DFS 돌자
    result = DFS(i, 0)

    # result가 최대 방문 수보다 크면 선배는 who에 저장하고, maxCount 갱신
    if result > maxCount :
        who = i
        maxCount = result

    # 최대 방문 수가 같다면 작은 선배 출력을 위해 who 갱신
    elif result == maxCount :
        if who > i :
            who = i

print(who)

---