난이도 : 실버 2
유형 : DFS
https://www.acmicpc.net/problem/24480
문제 접근
24479번
과 동일하되, 인접 노드를 작은수부터 큰수 순으로 방문하는 오름차순이 아닌 큰 수부터 작은 수 순으로 방문하는 내림차순 으로 방문하는 것이 차이이다.
그 전 코드를 활용하되, 내림차순으로만 정렬해주면 될 것 같다.
해답 및 풀이
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
# 1. 입력값을 입력받는다.
N, M, R = map(int,input().split())
edges = []
for _ in range(M):
u, v = map(int,input().split())
edges.append((u, v))
# 2. 입력받은 정보들로 그래프 구성하기
# 2-1. 그래프 구조 초기화
graph = []
for i in range(N + 1): # 0번 인덱스 노드를 사용하지 않기 위해 N+1 처리 해주는 모습
graph.append([])
# graph = [
# [], # 0번 인덱스 (사용 안함)
# [], # 1번 노드의 인접 노드
# [], # 2번 노드의 인접 노드
# [], # 3번 노드의 인접 노드
# [], # 4번 노드의 인접 노드
# [] # 5번 노드의 인접 노드
# ] 꼴이 됨.
# 2-2. 간선 정보 기반으로 인접 리스트 구성
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # 무방향 그래프니까 양방향 연결
# graph = [
# [], # 0번 (사용 안함)
# [2, 3], # 1번 노드 → 2, 3과 연결
# [1, 4], # 2번 노드 → 1, 4와 연결
# [1, 5], # 3번 노드 → 1, 5와 연결
# [2], # 4번 노드 → 2와 연결
# [3] # 5번 노드 → 3과 연결
# ] 가 됨.
# ++ 문제에서 인접노드는 오름차순으로 정렬하라고 했다.
for i in range(1 , N+1):
graph[i].sort(reverse=True)
# 3. 방문 여부를 체크할 리스트를 만든다.
visited = [False] * (N + 1) # 인덱스 0 을 안쓰기 위해 N+1 정의
# ++ 문제에서 원하길 각 정점이 몇 번째로 방문되었는지를 출력해야 한다.
order = [0] * (N + 1)
cnt = 1
# 4. DFS 함수(재귀)를 정의한다.
def dfs(node):
global cnt
visited[node] = True
order[node] = cnt
cnt += 1
for neighbor in graph[node]:
if not visited[neighbor]:
dfs(neighbor)
# 5. DFS 시작
dfs(R)
# 6. 결과 출력
for i in range(1, N + 1):
print(order[i])24479번과 동일한 코드에서 딱 ㅏㅎㄴ줄
graph[i].sort() 에서 graph[i].sort(reverse=True) 로 바꿔주었다.
sort 함수 안에 reverse=True 를 넣어주면 내림차순 정렬이 된다.
Frontend Engineers