이것이 취업을 위한 코딩 테스트다 CHAPTER 5 DFS/BF

• 탐색 
  • 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 자료구조
  • 데이터를 표현하고 관리하고 처리하기 위한 구조
• 오버플로
  • 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생
  • 즉, 저장 고안을 벗어나 데이터가 넘처흐를 때 발생
• 언더플로
  • 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태

 

DFS

• Depth-Frist Search
• 깊이 우선 탐색
• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
  • 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
• Stack
• O(N)

 

BFS

• Breadth Frist Search
• 너비 우선 탐색
• 가까운 노드부터 탐색하는 알고리즘
  • 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
• Que
• O(N)
• 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편

 

문제 3. 음료수 얼려먹기

        2차원 + 상하좌우 탐색

        ->BFS

       

        1. 구멍이 뚫린 지점 찾기

        2. 이 구멍과 연결된 부분 너비 우선 탐색으로 찾기

        반복

 

        DFS, BFS 둘다 가능

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

# 얼음 틀의 세로, 가로
N,M = map(int,input().split())

# 얼음 틀
ice = [list(map(int,input().rstrip())) for _ in range(N)]

# 아이스크림 수
cnt = 0
for r in range(N):
    for c in range(M):
        # 구멍인가?
        if ice[r][c] == 0:
            cnt += 1
            que = deque()
            que.append([r,c])
            while que:
                # 현 위치
                cr,cc = que.popleft()
                # 4방향 확인
                for dr,dc in [[1,0],[-1,0],[0,1],[0,-1]]:
                    nr = cr + dr
                    nc = cc + dc
                    # 범위 내 구멍
                    if 0 <= nr < N and 0 <= nc < M and ice[nr][nc] == 0:
                        ice[nr][nc] = 1
                        que.append([nr,nc])

print(cnt)

 

문제 4. 미로 탈출

    접근법 1

        4방향 이동+최소거리 -> BFS

        deque를 이용하여 4방향 확인하면서 조건(미로 내, 괴물이 없는지, 방문한 적 없는지)확인

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

# 미로 세로, 가로
N, M = map(int,input().split())
# 미로
miro = [list(map(int,input().rstrip())) for _ in range(N)]

def miro_escape(miro):
    # 방문 표시
    visited = [[0]*M for _ in range(N)]
    # [r,c,cnt]
    que = deque()

    # 시작 위치(0,0), 도착 위치(N-1,M-1)
    # 시작 위치 표시
    que.append([0,0,1])
    visited[0][0]=1

    while que:
        # 현재 위치, 몇번 이동했는지
        cr,cc,cnt = que.popleft()
        # 4방향 확인
        for dr,dc in [[1,0],[-1,0],[0,1],[0,-1]]:
            nr = cr + dr
            nc = cc + dc
            # 미로 내, 괴물이 없는지, 방문한 적 없는지
            if 0 <= nr < N and 0 <= nc < M and miro[nr][nc] == 1 and visited[nr][nc] == 0:
                # 도착?
                if nr == N-1 and nc == M-1:
                    return cnt+1
                # 방문 표시
                visited[nr][nc] = 1
                que.append([nr,nc,cnt+1])
  
print(miro_escape(miro))