옛날에는 나름 제일 자신있었는데,, 이제는 해도 해도 모르겠는 ` DFS & BFS ` ㅜㅜ

그래서 왜 그럴까 생각해봤는데, 역시 코딩테스트의 이론을 아는 것과 실제로 실전에 적용하는 것의

그 차이를 극복하기 힘들었던듯,, 그래서 오늘 코딩테스트에서는

DFS BFS 문제 하나만 맞추자 !!! 하는 마음으로 급하게 덤벼보기 😇😇 맨날 dfs bfs 연습할때

으악 왜안돼 ! -> 오 뭐야 이런거였냐 ~~~ -> 으악 왜 안돼 ! -> … 의 과정을 겪었는데,

이번에는 소소하게나마 작은 문제부터 내가 직접 다 구현해보고, 관련 문제도 풀어보기로 직접 고안해서 풀어보기로 했음 !!!

BFS

BFS 는 최단경로를 보장해야 할 때에 많이 쓰인당 !

queue를 이용하는데, list.pop(0)을 이용하면 내부적으로 더 시간이 많이 걸리므로,

collections.deque에서의 popleft() 를 많이 이용함 !

DFS

DFS는 빠르고 쉽게 탐색할때에 많이 쓰인다 !

stack을 이용하는데, 단순한 list를 이용해서 append(), pop()을 많이 한당

사실 알고리즘 문제를 풀 때에는 거의 재귀적인 dfs() 함수를 구현해서 많이 사용한다고..!


이번에는 문제도 풀어보자 !

  1. 백준 1260: DFS와 BFS로 !
def dfs(graph, index, visited):
    '''
    현재 graph 정보, 현재 index, visited 정보 , 전체 data의 개수 (with stack )
    '''
    # 현재 index를 방문했다고 표시하기
    visited[index] = 1
    print(index, end=' ')
    for i in range(1,n+1):
        # 현재 index의 숫자와 연결되어있는 node 중에서, 방문하지 않은 애들
        if graph[index][i] == 1 and visited[i] ==0:
                dfs(graph, i, visited)

from collections import deque
def bfs(graph, index, visited):
    q = deque()
    q.append(index)
    while q: # queue가 비어있을 때까지
        temp = q.popleft()
        if visited[temp] == 1: break
        visited[temp] = 1
        print(temp, end=' ')
        for i in range(1,n+1):
            if graph[temp][i] == 1 and visited[i] == 0:
                q.append(i)

#main                
n, m, v = map(int, input().split())
matrix=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    matrix[a][b]=matrix[b][a]=1

visited = [0]*(n+1)
dfs(matrix, v, visited)
print()
visited = [0]*(n+1)
bfs(matrix, v, visited)

test case는 전부 통과했는데 답은 틀렸다고 해서 굉장히 당황쓰,,

결론은 bfs에서, 중복으로 queue 안에 들어가는 애들을 건들여줬다!

def dfs(graph, index, visited):
    '''
    현재 graph 정보, 현재 index, visited 정보 , 전체 data의 개수 (with stack )
    '''
    # 현재 index를 방문했다고 표시하기
    visited[index] = 1
    print(index, end=' ')
    for i in range(1,n+1):
        # 현재 index의 숫자와 연결되어있는 node 중에서, 방문하지 않은 애들
        if graph[index][i] == 1 and visited[i] ==0:
                dfs(graph, i, visited)

from collections import deque
def bfs(graph, index, visited):
    q = deque()
    q.append(index)
    while q: # queue가 비어있을 때까지
        temp = q.popleft()
        #if visited[temp] == 1: break
        visited[temp] = 1
        print(temp, end=' ')
        for i in range(1,n+1):
            if graph[temp][i] == 1 and visited[i] == 0 and (i not in q):
                q.append(i)

#main                
n, m, v = map(int, input().split())
matrix=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    matrix[a][b]=matrix[b][a]=1

visited = [0]*(n+1)
dfs(matrix, v, visited)
print()
visited = [0]*(n+1)
bfs(matrix, v, visited)


  1. 백준 7576: 토마토

저번에 못다한 토마토 문제 풀기 !