DFS, BFS (백준1260dfsbfs , 백준2178미로찾기)

아직 DFS,BFS에 대한 풀이가 익숙하지가 않아서 좀더 공부를 해보기로 했다.
이해 될때 까지 계쏙해서 반복하기!!

백준 1260dfs,bfs

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

n,m,start=map(int,input().split())
visited=[False]*(n+1)

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


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

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

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

def bfs(start):
    q=deque([start])
    visited[start]=True
    while q:
        now=q.popleft()
        print(now,end=' ')
        for i in graph[now]:
            if not visited[i]:
                q.append(i)
                visited[i]=True
dfs(start)
visited=[False]*(n+1)
print()
bfs(start)

입력에 대해서 dfs와 bfs에대한 출력을 해줘야 하는 문제이다.
여기서 visited 가 겹치기 때문에 초기화를 해주거나, 다른변수로 지정해 주어야한다.

DFS 는 깊이 우선탐색 재귀함수나, 스텍을 이용해 구현
BFS 는 넓이 우선탐색 큐를 이용해서 구현

문제를 좀더 많이 풀어보고 복습하다 보면 개념이 어느정도 더 잡힐거 같다

미로탐색 백준2178

from collections import deque

n,m = map(int,input().split())

graph = []

for _ in range(n):
    graph.append(list(map(int, input())))

def bfs(x,y):
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]

    queue = deque()
    queue.append((x,y))

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if graph[nx][ny] == 0:
                continue
            
            if graph[nx][ny] ==1:
                graph[nx][ny] = graph[x][y] +1
                queue.append((nx,ny))

    return graph[n-1][m-1]

print(bfs(0,0))

해당 문제는 bfs 문제이다. 보통 최단경로 찾기 문제유형과 비슷한 문제이다
최단경로 같은 문제는 거의다 bfs 문제라고 보면 될 것 같다.
bfs 핵심은 큐를 이용해서 방문처리한 노드를 처리해 주는것

현재 알고리즘공부를 계속 하고 있는데 bfs, dfs , dp 에서 많이 막혀 있는 느낌이다.

이 알고리즘등은 문제를 계속해서 풀어보고 복습하는 법 밖에 없는 것 같다.