[이것이 취업을 위한 코딩 테스트다 with 파이썬] 3-2강(DFS , BFS, 음료수 얼려먹기, 미로 탈출)

DFS(Depth-First Search)

 

• DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
• DFS는 스택 자료구조(혹은 재귀 함수)를 이용한다.

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

 

2가 방문하면 2를 기준으로 다시 본다

# DFS 메서드 정의
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end = '')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]: # 방문하지 않은 노드들에 대해 방문 처리한다.
            dfs(graph, i, visited)
            
# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
     [], # 1번노드, 인덱스 0에 대한 내용은 비운다
     [2,3,8], # 1번 노드와 연결된 2,3,8 노드
     [1,7], # 2번 노드와 연결된 1,7 노드
     [1,4,5],
     [3,5],
     [3,4],
     [7],
     [2,6,8],
     [1,7]
]

# 각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9
# 모든 노드를 한번도 방문하지 않은 것 처럼 처리

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

# 12768345
 

전체 코드는 이코테 깃허브에 있다.

전체 코드는 이코테 깃허브에 있다.

---

BFS(Breadth-First Search)

• BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 탐색하는 알고리즘이다.
• BFS는 큐 자료구조를 이용한다. (각 언어마다 사용방법이 다르기 때문에 언어 숙지해야 한다.)
• 특정 경로에 대한 최단거리 문제를 풀 때 사용한다.

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

위에서 들어와서 아래로 나가는 방식

1은 방문했기 때문에 방문처리

가까운 노드부터 방문한 것을 확인할 수 있다.

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력하기
        v = queue.popleft() # 가장 먼저 들어온 원소를 꺼내준다.
        print(v, end= ' ')
        # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
          
# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
     [], # 1번 노드 / 인덱스 0에 대한 내용은 사용하지 않는다.
     [2,3,8], # 2번 노드와 연결 /  2, 3, 8노드와 인접
     [1,7],  # 3번 노드와 연결 / 1, 7노드와 인접
     [1,4,5],
     [3,5],
     [3,4],
     [7],
     [2,6,8],
     [1,7]
]

# 각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9
# 모든 노드를 한번도 방문하지 않은 것 처럼 처리

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

# 1 2 3 8 7 4 5 6
 

---

 

음료수 얼려 먹기

연결 구조 찾기 문제

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

# DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문
def dfs(x, y):
    # 주어진 범위를 벗어나는 경우에는 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    # 현재 노드를 아직 방문하지 않았다면
    if graph[x][y] == 0:
        # 해당 노드 방문 처리
        graph[x][y] = 1
        # 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
        dfs(x - 1, y) # 좌
        dfs(x, y - 1) # 하
        dfs(x + 1, y) # 우
        dfs(x, y + 1) # 상
        return True
    return False

# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
    for j in range(m):
        # 현재 위치에서 DFS 수행
        if dfs(i, j) == True:
            result += 1

print(result) # 정답 출력
# 3

+ java 코드는 이코테 깃허브에 있다.

---

미로 탈출

매번 새로운 지점을 방문할 때 이전 지점의 거리에서 +1을 해준다.

from collections import deque

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

# 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS 소스코드 구현
def bfs(x, y):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque()
    queue.append((x, y))
    # 큐가 빌 때까지 반복하기
    while queue:
        x, y = queue.popleft()
        # 현재 위치에서 4가지 방향으로의 위치 확인
        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]

# BFS를 수행한 결과 출력
print(bfs(0, 0))

전체 코드는 이코테 깃허브에 있다.