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

2023년 1월 20일에 작성됨

 

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

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

 

 

문제 분석

깊이 우선 탐색 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. 1부터 n까지 반복하여 선배들의 대답을 입력받고 graph 리스트에 추가한다.

2. start (처음 시작한 선배의 번호)를 매개변수로 하는 dfs 함수를 선언하는데, visit 리스트에 해당 start는 True로 방문 처리를 해준다.
만약, graph[start]가 false라면 방문하지 않은 노드이므로 dfs 함수를 해당 위치로 하여 호출한다.

3. 1부터 n까지 반복하여 물어본 선배인지 체크할 리스트 visit을 생성하고 false로 초기화 해준다.

4. 1부터 n까지 모든 선배의 번호를 매개변수로 하여 dfs 함수를 호출해주고, 각 선배의 대답의 개수인 visit 안의 true의 개수를 세어서 result 리스트에 넣어준다.

5. 마지막으로 result 요소 중 최댓값(최대한 많은 선배에게 물어본 경우)이 result 리스트에서 몇 번째 인덱스에 있는지(최대인 경우의 물어볼 선배의 번호) 출력해준다.

 

 

 

end

bfs, dfs를 코드로 직접 구현하는 것이 아직 어렵다..
나도 문제에 맞게 요리조리 코드를 짤 수 있는 멋진 사람이 되고 싶다ㅜㅜ!!