파이썬 알고리즘 232번 | [백준 1260번] DFS 와 BFS - 트리 복습 날

233 . DFS 와 BFS

1) 어떤 전략(알고리즘)으로 해결?

• bfs, dfs

2) 코딩 설명

<내 풀이>

from collections import deque
import sys
import copy

n,m,v = map(int , sys.stdin.readline().rstrip().split())
dict={}
for j in range(n) :
    dict[j+1]=[]

for i in range(m) : 
    a,b = ((map(int , sys.stdin.readline().rstrip().split())))
    dict[a].append(b)
    dict[b].append(a)

for k in dict : 
    dict[k].sort()

dict2 = copy.deepcopy(dict)


visit1 = [0 for _ in range(n+1)]

def dfs(rel, v) :
    print(v, end=" ")
    if rel[v] : 
        visit1[v] = 1
        for rval in rel[v] :
            if visit1[rval] == 0 :
                dfs(rel, rval)

visit2 = [0 for _ in range(n+1)]

def bfs(rel, v) :
    q = deque()
    q.append(v)
    visit2[v] = 1
    while q :
        v = q.popleft()
        print(v, end=" ")
        for val in rel[v] :
            if visit2[val]==0 :
                q.append(val)
                visit2[val] = 1

dfs(dict, v)
print()
bfs(dict, v)

틀린 풀이

• break를 걸어서 틀렸었다.

from collections import deque
import sys
import copy

n,m,v = map(int , sys.stdin.readline().rstrip().split())
dict={}
for j in range(n) :
    dict[j+1]=[]

for i in range(m) : 
    a,b = ((map(int , sys.stdin.readline().rstrip().split())))
    dict[a].append(b)
    dict[b].append(a)

for k in dict : 
    dict[k].sort()

dict2 = copy.deepcopy(dict)


visit1 = [0 for _ in range(n+1)]

def dfs(rel, v) :
    print(v, end=" ")
    if rel[v] : 
        visit1[v] = 1
        for rval in rel[v] :
            if visit1[rval] == 0 :
                dfs(rel, rval)
                break 

visit2 = [0 for _ in range(n+1)]

def bfs(rel, v) :
    q = deque()
    q.append(v)
    visit2[v] = 1
    while q :
        v = q.popleft()
        print(v, end=" ")
        for val in rel[v] :
            if visit2[val]==0 :
                q.append(val)
                visit2[val] = 1

dfs(dict, v)
print()
bfs(dict2, v)

<반성 점>

• 이차원 배열에 저장할걸!
• 사전으로 다루니깐 까다로웠다.
• 그리고 사전 복사는 copy.deepcopy 로 진행하자!
• dfs, bfs 좀만 안하면 바로 까먹어버리네, 오늘 필수 문제랑 스도쿠 까지 하고 다 주석달아버리자

<배운 점>

• 오랜만에 bfs , dfs 다시 복습 손코딩