아직 최적화가 안되어 있습니다. 😂
두 문제 사실상 똑같은 방법으로 풀었다. 16940 코드 복붙하고 bfs 돌리는 부분만 dfs로 바꿨더니 통과 되는걸? 개꿀쓰
문제가 뭐였지?
정답이 여러개인 경우 이렇게 채점한다나..? 스페셜 저지라고 한단다.
요런식으로 첫째 줄에 정점의 개수 N, 그리고 n-1번 줄 까지 간선이 연결되어 있는 경우가 주어진다. 그래프는 양방향이다.
이제 이걸 bfs로 돌릴 건데, bfs로 돌리면 사실상 큐에 어떤 순서로 담기냐에 따라서 순서가 여러개가 될 수도 있다.
그리고 마지막으로, 유저가 입력한 bfs 경로가 주어지고, 이 경로가 올바른 경로인지 아닌지를 판단하는 것이 문제이다.
어디서 해맸지?
이거부터 봐야겠다.
bfs 스페셜 풀 때는 많이 해맸는데...이건 아래에서 말해보도록 하고.
여러가지를 생각해봤다. 부모 자식 관계를 잘 따지면 될 것 같기도 하고..... 주어진 순서를 기반으로 역추적을 할 수 있을까도 따져보고..
맨 처음 생각은 다음과 같았다.
-
bfs 과정을 생각해 보면, 인접리스트에 순서가 어떻게 담기냐에 따라서 방문 순서가 달라진다.
-
그러면 아예 bfs를 재귀로 돌리면서, 인접리스트의 순서를 순열로 만들어서 각자 재귀를 다 돌려버리고
-
끝났을 때 ans_list에다가 지금까지 쌓여온 문자열들을 다 담고 이거를 입력받은 경로랑 비교하면 되지 않을까
=> 완전탐색. 당연히 시간초과😥. 거기다가 deepcopy까지 쓰니 메모리초과. 하지만 올려놓는다... 이 또한 과정이니까...
"""
매우 드럽고 시간초과 나는 코드입니다.
"""
import sys
from collections import deque
from itertools import permutations
from copy import deepcopy
input = sys.stdin.readline
ans_list = []
def bfs(n,now_string,tree,q,visited) :
if len(now_string) == n :
ans_list.append(now_string)
return
if q :
front = q.popleft()
combi = list(permutations(tree[front],len(tree[front])))
for c in combi :
temp = list(c)
new_q = deepcopy(q)
new_visit =deepcopy(visited)
new_string = now_string
for k in temp :
if new_visit[k] == False :
new_visit[k] = True
new_string += str(k)
new_q.append(k)
bfs(n,new_string,tree,new_q,new_visit)
def solve(n, tree, order) :
visited = [False for i in range(n+1)]
q = deque()
q.append(1)
visited[1] = True
bfs(n,"1",tree,q,visited)
order_cmp = order.replace(" ","").rstrip()
for s in ans_list :
if s == order_cmp :
print(1)
return
print(0)
if __name__ == "__main__" :
n = int(input())
tree = [[] for _ in range(n+1)]
for _ in range(1,n) :
x,y = map(int,input().split())
tree[x].append(y)
tree[y].append(x)
order = input()
solve(n,tree,order) 이와 더불어 삽질 n스택 정도 까지는 아니고 더 하다 보니까 훨씬 쉬운 방법이 있었다.
어떻게 풀었지?
결국 중요한건 인접리스트 각각의 원소 안에 들어있는 순서. 그러면 입력받은 경로를 잘 따져보면, 어떤 정점이 더 우위를 갖고 있는지 알 수 있다!
그냥 먼저 방문됐다? 그러면 그게 더 높은 우선 순위를 가지고 있는거고, 그 우선순위에 따라서 인접리스트를 정렬한다.
그리고 그에따라서 bfs 돌리고 나온 결과값과 입력받은 결과값 확인. 통과 ㅠㅠ
import sys
from collections import deque
input = sys.stdin.readline
ans_list = []
def solve(n, tree, order) :
visited = [False for i in range(n+1)]
q = deque()
q.append(1)
visited[1] = True
rank = [-1 for i in range(n+1)]
for i in range(1,n+1) :
rank[order[i-1]] = i
for i in range(1,n+1) :
tree[i] = sorted(tree[i], key=lambda x : rank[x])
while q :
front = q.popleft()
ans_list.append(front)
for element in tree[front] :
if visited[element] == False :
visited[element] = True
q.append(element)
if ans_list == order :
print(1)
else :
print(0)
if __name__ == "__main__" :
n = int(input())
tree = [[] for _ in range(n+1)]
for _ in range(1,n) :
x,y = map(int,input().split())
tree[x].append(y)
tree[y].append(x)
order = list(map(int,input().split()))
solve(n,tree,order) 해놓고 다른사람들은 어케 풀었나 궁금해서 찾아보니까 방법이 많은 것 같다..
embeddedjune님 velog
내가 생각한거랑 거의 똑같이 푸셨는데 설명을 엄청 잘 해주셨다. 세상엔 잘하는 사람이 정말 많은 것 같다.
문제가 뭐였지?
위랑 거의 똑같고, 다만 dfs일 뿐이다.
dfs도 결국 인접리스트의 순서가 중요하다고 생각하면, bfs랑 아예 똑같은 풀이가 가능하다.
위 코드 고대로 두고 결과값 확인 부분만 dfs로 바꿔주면 끝
import sys
input = sys.stdin.readline
ans_list = []
def dfs(node, visited, tree) :
if(visited[node] == True) :return
visited[node] = True
ans_list.append(node)
for element in tree[node] :
if visited[element] == False :
dfs(element,visited,tree)
def solve(n, tree, order) :
visited = [False for i in range(n+1)]
rank = [-1 for i in range(n+1)]
for i in range(1,n+1) :
rank[order[i-1]] = i
for i in range(1,n+1) :
tree[i] = sorted(tree[i], key=lambda x : rank[x])
dfs(1,visited,tree)
if ans_list == order :
print(1)
else :
print(0)
if __name__ == "__main__" :
n = int(input())
tree = [[] for _ in range(n+1)]
for _ in range(1,n) :
x,y = map(int,input().split())
tree[x].append(y)
tree[y].append(x)
order = list(map(int,input().split()))
solve(n,tree,order)
거의 1+1문제. 개꿀
