[python]1260번 DFS와 BFS, print문 end 사용으로 최적화

나의 풀이

 

import sys
from collections import deque
sys.setrecursionlimit(12345)
input = sys.stdin.readline
que = deque()
dot,relat,start = map(int,input().split())
graph = [[]for i in range(dot+1)]
for i in range(relat):
    fst,scd = map(int,input().split())
    graph[fst].append(scd)
    graph[scd].append(fst)
for i in range(1,dot+1):
    if graph[i]:
        graph[i].sort()
visit = [0 for i in range(dot+1)]
rstd = []
rstb = []
def dfs(idx):
    rstd.append(idx)
    for next in graph[idx]:
        if not visit[next]:
            visit[next] = 1
            dfs(next)
            
def bfs():
    while que:
        cur=que.popleft()
        rstb.append(cur)
        for next in graph[cur]:
            if not visit[next]:
                visit[next]=1
                que.append(next)
visit[start] = 1
dfs(start)
visit = [0 for i in range(dot+1)]
visit[start]=1
que.append(start)
bfs()
print(*rstd)
print(*rstb)

함수로 만들어 각각 한번씩 따로 실행되도록 만들었다.

다른 사람 풀이를 보니 print문을 사용하는게 자꾸 너무 아쉽다.

 

 

from collections import deque
import sys
input=sys.stdin.readline

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

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

for i in range(1,len(graph)) :
  graph[i].sort()

def dfs(x) :
  visit1[x]=1
  print(x,end=' ')
  for i in graph[x] :
    if visit1[i]==0 :
      dfs(i)

def bfs(x) :
  q=deque()
  q.append(x)
  visit2[x]=1
  while q :
    x=q.popleft()
    print(x,end=' ')
    for i in graph[x] :
      if visit2[i]==0 :
        q.append(i)
        visit2[i]=1

dfs(v)
print()
bfs(v)

따로 변수에 방문한 정점의 값을 append하지 않고 바로 출력한다. print(end=" ")를 통해 출력 후 새 줄이 아닌 공백 한칸 띄우고 출력하게 만들었다.

끝에 print()는 의도적으로 \n을 만들어 dfs값과 bfs값을 나누게 하였다.