[문제 풀이] 7월 27일

 

< 1260: DFS와 BFS > - 백준

 

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

n, m, v = map(int, input().split()) # 정점의 개수, 간선의 개수, 시작 정점 번호

graph = [[0] * (n + 1) for _ in range(n + 1)] 
# 각 노드가 방문된 정보 list
list = [0] * (n + 1)  # bfs
list2 = [0] * (n + 1)  # dfs

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

def bfs(v):
  q = deque()
  q.append(v)       
  list[v] = 1  # 현재 노드 방문
  while q:  # 큐가 빌 때까지
    v = q.popleft()
    print(v, end = " ")
    # 아직 방문하지 않은 인접한 노드를 모두 큐에 삽입
    for i in range(1, n + 1):
      if list[i] == 0 and graph[v][i] == 1:
        q.append(i)
        list[i] = 1

def dfs(v):
  list2[v] = 1  # 현재 노드 방문      
  print(v, end = " ")
  for i in range(1, n + 1):
    if list2[i] == 0 and graph[v][i] == 1: # 아직 방문 전이고, 인접한 노드이면 재귀 호출
      dfs(i)



dfs(v)
print() # 줄바꿈 필요
bfs(v)

 

• 깊이 우선 (DFS) : 함수 재귀
  1. 탐색시작노드를 스택에 삽입하고 방문처리를 한다.
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  3. 더 이상 2번의 과정을 수행할 수 없을때까지 반복

• 넓이 우선 (BFS) : 큐, 데크
  1. 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다.
  2. 큐에서 노드를 꺼낸 뒤에 해당노드의 인접노드중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

 

 

< 게임 맵 최단 거리 > - 프로그래머스

 

from collections import deque

def solution(maps):
    answer = 0
    n = len(maps) # 세로
    m = len(maps[0])  # 가로
    dx = [-1, 1, 0, 0] # 왼 오 아래 위
    dy = [0, 0, -1, 1]

    def bfs(x,y):
        q = deque()
        q.append((x,y))

        while q:
            x, y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if nx < 0 or ny < 0 or nx >= n or ny >= m:  # 범위 벗어남
                    continue
                if maps[nx][ny] == 0:  # 벽이 있음
                    continue
                if maps[nx][ny] == 1:  # 벽이 없음
                    maps[nx][ny] = maps[x][y] + 1
                    q.append((nx, ny))
        return maps[n-1][m-1]

    if bfs(0,0) == 1:
        return -1
    else:
        answer = bfs(0,0)

    return answer