[구름LEVEL] 행성을 관측하는 할아버지의 이야기

문제

https://level.goorm.io/exam/49082/%ED%96%89%EC%84%B1%EC%9D%84-%EA%B4%80%EC%B8%A1%ED%95%98%EB%8A%94-%ED%95%A0%EC%95%84%EB%B2%84%EC%A7%80%EC%9D%98-%EC%9D%B4%EC%95%BC%EA%B8%B0/quiz/1

풀이

dfs를 활용한 풀이
인접리스트 방식으로 해당 행성보다 작은 행성들의 인덱스를 저장한다.
문제에는 직접 언급하지 않았지만 입력값으로 중복된 값을 주어질 수도 있기 때문에
인접리스트 방식을 사용하되 set() 을 사용했다.

1번 행성부터 N번 행성까지 dfs를 실행한다.
자신의 크기보다 작은 행성에 방문하지 않았으면 재귀적으로 방문한다.

dfs 함수 파라미터에는 맨처음 시작 행성의 인덱스인 start 를 가지고 있다.

방문할 수 있는 행성이 있다면 start 보다 작은 행성임을 의미하므로
answer[start][1] 의 값을 1 증가 시킨다.

방문된 행성은 방문될때마다 자기보다 큰 행성이 존재함을 의미하므로
answer[next_pl][0] 의 값을 1 증가 시킨다.

이때 answer[i][0] 은 i 행성보다 큰 행성의 개수를,
answer[i][1]은 i 행성보다 작은 행성의 개수를 저장하고 있다.

모든 dfs를 마친다면 결과를 출력한다.

N, M = map(int, input().split(" "))
map_down = [set() for _ in range(N+1)]

for _ in range(M):
	x, y =  map(int, input().split(" "))
	map_down[x].add(y)
	
def dfs(start, now_pl, answer, map_pl, visited):
	for next_pl in map_pl[now_pl]:
		if not visited[next_pl]:
			answer[next_pl][0] += 1
			answer[start][1] += 1
			visited[next_pl] = True
			dfs(start, next_pl, answer, map_pl,visited)
	return

def solution(N,M,map_down):
	answer = [[0,0] for _  in range(N+1)]
	for start in range(1, N+1):
			visited = [False] * (N+1)
			dfs(start,start, answer, map_down,visited)
	
	for i in range(1, N+1):
		print(answer[i][0], answer[i][1])
	return
	
solution(N, M, map_down)