[Python]백준_3182 : 한동이는 공부가 하기 싫어!

Alal11·2023년 1월 20일

출처

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

문제

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

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

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

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

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

입력

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

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

출력

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

예제 입출력

알고리즘 분류

그래프 이론
브루트포스 알고리즘
그래프 탐색

➡️문제 분석

깊이 우선 탐색 dfs를 이용하여 최대한 많은 선배에게 물어보려면 어느 선배한테 물어봐야 하는지 구하는 문제이다.

➡️코드(⭕)

import sys
input = sys.stdin.readline

n = int(input())
graph = [0]
result = [0]

for i in range(1, n+1):
    graph.append(int(input()))

# 깊이 우선 탐색(dfs) 알고리즘 함수 정의
def dfs(start):
    # dfs를 사용해서 시작점부터 어디까지 갈 수 있는지 체크
    visit[start] = True             # start 인덱스의 위치는 이미 물어본 선배로 체크
    if not visit[graph[start]]:     # visit[graph[start]]가 False라면 아직 안물어본 선배
        dfs(graph[start])


for i in range(1, n+1):
    visit = [False]*(n+1)    # 물어본 선배인지 체크할 배열 (False로 초기화)
    dfs(i)
    result.append(visit.count(True))    # visit안의 True의 개수가 i번째 선배의 대답 개수

# result의 최댓값이 result 리스트에서 몇번째 인덱스인지 출력
print(result.index(max(result)))

➡️코드 분석

1부터 n까지 반복하여 선배들의 대답을 입력받고 graph 리스트에 추가한다.
start (처음 시작한 선배의 번호)를 매개변수로 하는 dfs 함수를 선언하는데, visit 리스트에 해당 start는 True로 방문 처리를 해준다.
만약, graph[start]가 false라면 방문하지 않은 노드이므로 dfs 함수를 해당 위치로 하여 호출한다.
1부터 n까지 반복하여 물어본 선배인지 체크할 리스트 visit을 생성하고 false로 초기화 해준다.
1부터 n까지 모든 선배의 번호를 매개변수로 하여 dfs 함수를 호출해주고, 각 선배의 대답의 개수인 visit 안의 true의 개수를 세어서 result 리스트에 넣어준다.
마지막으로 result 요소 중 최댓값(최대한 많은 선배에게 물어본 경우)이 result 리스트에서 몇 번째 인덱스에 있는지(최대인 경우의 물어볼 선배의 번호) 출력해준다.