(백준) 1260. DFS와 BFS / python / 문제 해결

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

1260번: DFS와 BFS

 

from collections import deque

def dfs(graph,v,visited):
  visited[v]=True
  print(v, end=" ")
  for i in graph[v]:
    if not visited[i]:
      dfs(graph,i,visited)

def bfs(graph,v,visited):
  queue=deque([v])
  visited[v]=True
  while queue:
    node=queue.popleft()
    print(node,end=' ')
    for i in graph[node]:
      if not visited[i]:
        queue.append(i)
        visited[i]=True


n,m,v=map(int, input().split())
graph=[[] for _ in range(0,n+1)]

#양 방향의 간선
for _ in range(m):
  a,b=map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

#두 노드를 잇는 간선이 중복되서 들어올 수 있기 때문에 set()으로 중복제거
#숫자가 작은 노드를 먼저 선택해야 하므로 그래프를 정렬했다. 
for i in range(n+1):
  graph[i]=sorted(list(set(graph[i])))

print(graph)

visited=[False]*(n+1)
dfs(graph,v,visited)
print()
visited=[False]*(n+1)
bfs(graph,v,visited)

정석 코드 그대로 dfs는 재귀로 풀고 bfs는 큐로 풀면 된다. 

왜 이렇게 많이 틀렸냐 하면 

 

1. 오타를 낸 상태로 그대로 제출

2. 양 방향 간선임을 고려 안 하고 제출 

3. 같은 간선이 중복으로 들어오는 경우와 그 간선을 방문할 때 작은 숫자를 먼저 방문해야 하는 경우를 고려하지 못함 

 

이 세가지를 해결하니 무난하게 맞출 수 있었다. 꼼꼼히 하자