1260. DFS와 BFS

Leethub로 풀이를 깃헙에 바로 올리려 했는데, 잘 안되서 백준으로 갈아탔다ㅋㅋ
다행히 백준허브는 잘 작동 되는듯.

계속 DFS&BFS 위주의 문제를 보고있다.
예전에도 풀었지만 새로운 방법으로 접근해보려고 한다.

from collections import deque

node, edge, start = map(int,input().split())
graph = []

for i in range(edge):
  route = list(map(int, input().split()))
  
  graph.append(route)

graph.sort(key = lambda x:(x[0],x[1]))

result_dfs = []

def dfs(start):
  if start not in result_dfs:
    result_dfs.append(start)
    for route in graph:
      if route[0] == start:
        dfs(route[1])
      if route[1] == start:
        dfs(route[0])

result_bfs = []

def bfs(start):
  qq = deque()
  qq.append(start)    
  
  while qq:
    temp = qq.popleft()
    
    if temp not in result_bfs:
      result_bfs.append(temp)
      for route in graph:
        if route[0] == temp:
          qq.append(route[1])
        if route[1] == temp:
          qq.append(route[0])
        
dfs(start)
bfs(start)

print(result_dfs)
print(result_bfs)

사실 BFS&DFS 라는 큰 틀은 벗어나지 않지만, 접근하는 방식을 틀어봤다.
대부분 다 visited라는 리스트를 통해 방문한 노드인지를 기록하는데, 그냥 바로 반환값을 만들면 되지 않을까 싶어서 시도해 보았는데,
당연히 잘 안된다ㅎㅎ
어디서 틀려먹은건지 좀 시간을 두고 봐봐야겠다.

아래의 코드는 예전에 내 풀이다. 특별한거 없이 여느 블로그에나 굴러다니는 정석적인 풀이다.

from collections import deque

def bfs(graph, v, visited):
  queue = deque([v])

  visited[v] = True

  while queue:
    v = queue.popleft()
    print(v,end=' ')

    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True

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

nodes, vertices, start = map(int, input().split())

graph = [[] for i in range(nodes+1)]

for i in range(vertices):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

for i in graph:
  i.sort()
visited = [False]*(nodes+1)

dfs(graph, start, visited)
print('\n', end='')
visited = [False]*(nodes+1)

bfs(graph, start, visited)