백준 #1260

난이도 : 실버2
소요시간 :  57분
사용한 풀이법 : dfs_재귀, bfs_큐

---

풀이 과정

1. 입력받은 n값에 대한 탐색용 배열 생성 후 false 초기화
2. bfs, dfs 각각의 방문 탐색용 배열 생성 후 false 초기화
3. m에 대해 반복문 돌리면서 입력된 값들에 해당하는 인덱스 값 True 변환
   1. 각각의 행의 값들 중 True값은 연결된 엣지의 번호를 뜻함
   2. ex) 1번 행의 3,4열이 true이면, 1-3/1-4 연결된 것!
4. bfs는 큐를 이용한 풀이
   1. python 특성상 queue보다 deque가 효율적이라서 deque사용
5. dfs는 재귀를 이용한 풀이
   1. 스택으로 할라다가 실패함ㅎ..

작성 코드

from collections import deque
n,m,v = map(int, input().split(' '))

g=[[False]*(n+1) for _ in range(n+1)] # 탐색용 그래프 배열 false 초기화
bfs_vis = [False]*(n+1) #bfs용 방문 체크 
dfs_vis = [False]*(n+1) #dfs용 방문 체크


for _ in range(m):
    a,b = map(int,input().split(' '))
    g[a][b] = True
    g[b][a] = True

def bfs(v):
    q = deque([v])
    bfs_vis[v]=True
    while q:
        v = q.popleft()
        print(v,end=' ')
        for i in range(n+1):
            if bfs_vis[i] == False and g[v][i] == True :
                q.append(i)
                bfs_vis[i] = True

def dfs(v,cnt):
    dfs_vis[v] = True
    print(v,end=' ')
    if cnt == n: return 
    for i in range(n+1):
        if dfs_vis[i]== False and g[v][i] == True :
            cnt += 1
            dfs(i,cnt)
                 
dfs(v,0)
print("")
bfs(v)

피드백

dfs를 스택으로 풀고싶었는데 사고가 더 안돌아가서 그냥 재귀로 풀었다
원래는 c++사용자 이지만 python으로 한번 해봤는데 뭔가 더 잘풀리는거 같다. 사용언어 바꿔볼까나..