[백준] 16940, 16964: BFS 스페셜저지 , DFS 스페셜저지

문제: BFS 스페셜저지
DFS 스페셜저지

이 문제의 핵심 : lambda는 리스트 우선순위로도 정렬이 가능하다!

처음 BFS 스페셜 저지 문제를 풀 때는 각 뎁스마다 카운트를 증가시켜서 큐에 들어가는 노드에 (값, 깊이)를 넣고 깊이가 정렬되어 있으면 통과하도록 했다. 그런데 이때는 같은 뎁스라도 먼저 들어간 부모 노드에 따라 자식 노드의 우선순위가 결정된다는 것을 간과했다.

그래서 같은 깊이의 노드라도 ,노드가 들어간 순서대로 자식 노드의 우선순위를 결정해주기 위해 , 입력 마지막 줄을 통해 우선순위를 부여하는 리스트를 만들고 1~ n 까지의 자식 리스트가 우선순위대로 정렬될 수 있도록 했다. 그 후 DFS, BFS를 돌렸다.

graph[i].sort(key=lambda x:arraySort[x]) 

그리고 또 하나 고려해야 할 것은 여기서 "큐에 시작 정점을 넣는다. 이 문제에서 시작 정점은 1이다. 1을 방문했다고 처리한다."
즉, 입력 값의 마지막 줄에서 시작점이 1이 아니면 틀리는데 이 조건을 빼먹으면 안된다!

스페셜 저지를 만들 때는 정렬 먼저 -> 그래프 시작!

16940: BFS 스페셜저지

import sys
from collections import deque
n = int(input())
graph = [[]*(n+1) for _ in range(n+1)]
for i in range(n-1):
	a, b = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)
compare = list(map(int, input().split()))
visited = [False] * (n+1)
answer = []
#여기까지는 일반적인 bfs
def bfs(start, graph, visited):
	q = deque()
	q.append(start)
	visited[start] = True
	while q:
		x = q.popleft()
		answer.append(x)
		for i in graph[x]:
			if not visited[i]:
				q.append(i)
				visited[i] = True
#시작점이 1이 아니면 틀림 
if compare[0] != 1:
	print(0)
	exit()
arraySort = [0]*(n+1)
# 우선순위 부여 
for i in range(len(compare)):
	arraySort[compare[i]] = i
# 우선순위 리스트대로 자식 리스트 정렬
for i in range(1, len(graph)):
	graph[i].sort(key=lambda x:arraySort[x])
# 그 후에 돌림 
bfs(1, graph, visited)
if answer == compare:
	print(1)
else:
	print(0)

16964: DFS 스페셜저지

import sys
input = sys.stdin.readline
n = int(input())
graph = [[] for _ in range(n+1)]
for i in range(n-1):
	a, b = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)
compare = list(map(int, input().split()))
visited = [False] * ( n+1)
answer = []
#여기까지는 일반적인 dfs
def dfs(graph, i, visited):
	visited[i] = True
	answer.append(i)
	for v in graph[i]:
		if not visited[v]:
			dfs(graph, v, visited)
			visited[v] = True
#우선순위 부여 
arraySort = [0] * (n+1)
for i in range(len(compare)):
	arraySort[compare[i]] = i
# 1이 아니면 틀림 
if compare[0] != 1:
	print(0)
	exit()
# 정렬
for i in range(1, len(graph)):
	graph[i].sort(key=lambda x : arraySort[x])
# dfs 돌림
dfs(graph, 1, visited)
if answer == compare:
	print(1)
else:
	print(0)