1. 탐색(Search)

탐색은 많은 데이터들 가운데 원하는 데이터를 찾아가는 과정이다.

2. BFS

BFS는 넓이 우선 탐색이라고 불리며 그래프에서 가장 가까운 곳부터 탐색하여 출력 혹은 연산하는 알고리즘이다. BFS를 구현하기 위해서 선입선출 방식인 '큐' 자료구조를 사용하는 것이 일반적이다. 가장 가까운 노드부터 큐에 넣어 가장 먼저 출력될 수 있도록 하여 점차 멀리 있는 노드로 차례로 탐색이 된다. 이때 이미 방문한 노드는 다시 재방문하지 않도록 설정을 해주어야 하며, 가장 가까운 노드가 2개 이상이 주어질 때에는 어떤 순서(낮은 값부터, 높은 값부터)를 지켜가며 탐색할 것인지도 설정해야 한다. 위 그림은 시작 노드인 1이 큐에 삽입된 후 출력이되어 방문할 수 있는 곳을 찾아 큐에 삽입한다. 그리고 큐에 들어온 순서대로 노드 번호가 출력되어 나오면서 출력된 노드와 연결된 노드의 번호를 큐에 삽입한다. 이런 방식으로 가장 가까운 노드부터 찾아가 그 노드를 큐에 삽입하는 형식이다.
그림은 level로 탐색할 때 가장 낮은 level로 탐색하는 것을 볼 수 있다.
그림은 값이 낮은 순서부터 탐색해 나가는 형식이다. 그래프(트리)형식은 인접 행렬이 뿐만 아니라 인접 리스트나 배열 리스트도 문제 설정이 될 수 있다. 중요한 것은 문제의 조건에 따라서 현재 조건에서 해결 할 수 있는 가장 가까운 부분부터 방문하여 진행하기 때문에 BFS를 '최단거리'찾기 알고리즘이라 부르기도 한다.
문제를 살펴보며 좀 더 자세히 알아보자. 이번 문제는 인접 행렬인 2차원 그래프 탐색이다.

3. 구현

구현은 문제가 주어질 때, 문제를 해결하기 위한 알고리즘이나 생각나는 아이디어를 코딩할 수 있는 능력을 말한다. 생각해낸 풀이 방법을 파이썬으로 정확하게 구현할 수 있어야 하며 이는 평소에 얼마나 자주 문제들을 접하고 풀어보았는지 검증하는 것이기도 하다. 이것은 BFS형식의 문제뿐만이 아니라 다양한 문제에서 제시하는 조건에 맞춰 코딩을 할 수 있는가를 묻는 것이기에 다양한 문제들 속에 있는 탐색 방법이나 아이디어들을 많이 접할 수록 문제를 해결할 수 있는 가능성이 높아진다. 이번 문제에서는 BFS 탐색을 할 때, 동서남북으로 점진적으로 확장하면서 탐색하는 방법이기에 현재 노드에서 동서남북을 확인하며 진행하는 구현을 할 수 있어야 한다. 이런 현재 노드에서 상하좌우 뿐만 아니라 대각선을 탐색하는 문제도 자주 등장하기에 어떤 식으로 탐색을 하며 진행하는지 살펴보겠다.

4.1 문제

n×n 크기의 2차원 배열이 주어지며, 0과 1로 이루어져 있다. 1은 섬이며 0은 바다이다. 그리고 n×n의 바깥은 모두 바다이다. 섬과 섬 사이는 상하좌우로 이어져있으며, 바다가 없다면 섬은 기본적으로 다리가 놓여 있다. 섬들은 떨어져 있거나 연결되어 있있는데, 섬 좌표 (0, 0)에서 시작하여 (n, n)까지 가장 빠르게 가려면 몇 번의 섬을 이동해야 하는지 출력하시오.
7×7 크기로, 출발점은 (0, 0) 도착점은 (6, 6)이다.

입력:
1, 1, 0, 1, 0, 1, 0
1, 1, 0, 0, 1, 1, 0
1, 1, 1, 0, 0, 1, 1
1, 1, 0, 0, 1, 1, 0
1, 0, 1, 1, 1, 0, 1
1, 1, 1, 0, 1, 1, 1
1, 0, 1, 1, 0, 1, 1

4.2 풀이

섬 찾기 문제는 이전 챕터의 엘리베이터 문제와 비슷하다. 현재의 섬에서 한 번에 갈 수 있는 다음 모든 섬을 탐색한 후, 다음 섬에서 다시 한 번에 갈 수 있는 모든 섬을 탐색해 나가는 식이다. 다른 것은 엘리베이터 문제는 -2, -5, +2 만 움직일 수 있었다면, 이번엔 상하좌우를 탐색하며 바다인지 아닌지 확인해야 하는 것이 추가되었다.
1. 입력[x][y]가 2차원 리스트로 입력되면, x는 행, y는 열을 나타낸다.
2. 출발[0][0]에서 밑으로 한 칸 내려간다면 '밑지점[1][0] = 출발[0+1][0]'이므로 출발 지점에서 상하좌우를 탐색하는 코드를 구현해야한다.
3. 섬 크기과 같은 2차원 체크 배열을 미리 생성하여 방문을 한 섬인지 아닌지 체크해야 하며 거리를 입력할 수 있는 2차원 배열도 생성한다.
4. 시작지점에서 시작하여 상하좌우를 탐색하는데, 도착점이 오른쪽 아래에 있다고 해서 오른쪽과 아래만 탐색하면 도착할 수 없기에 동서남북 모두 확인한다. 동서남북이 바다가 아니며 방문한 적이 없는 섬이라면 진출하도록 한다.
5. 도착 지점에 도달하면 함수를 종료시키고 몇 번 만에 도착하였는지 출력한다.

from collections import deque # 큐자료형 deque 사용.
def BFS(island):
    while dQ:
        x, y = dQ.popleft()# 출발지점의 좌표를 꺼낸다.
        if x == n - 1 and y == n - 1: # 도착지점
            return dist[x][y]
        for k in range(4):# 동서남북 4군대 좌표 대조
            nx = x + dx[k]
            ny = y + dy[k]
            # 4군데의 좌표가 2차원 표를 벗어나지 않아야 하며, 섬인지 바다인지 확인, 방문하지 않은 섬이라면 큐에 삽입한다.
            if 0 <= nx < n and 0 <= ny < n and island[nx][ny] == 1 and chArr[nx][ny] == 0:
                dQ.append((nx, ny))# 큐에 입력된 섬의 좌표는 다시 출발지점이 되어, while문을 통해 출력되며 점점 퍼져나간다.
                chArr[nx][ny] = 1 # 방문한 섬은 체크
                dist[nx][ny] = dist[x][y] + 1 # 이동 거리는 이전 섬의 거리에서 + 1
if __name__ == '__main__':
    island = [
        [1, 1, 0, 1, 0, 1, 0],
        [1, 1, 0, 0, 1, 1, 0],
        [1, 1, 1, 0, 0, 1, 1],
        [1, 1, 0, 0, 1, 1, 0],
        [1, 0, 1, 1, 1, 0, 1],
        [1, 1, 1, 0, 1, 1, 1],
        [1, 0, 1, 1, 0, 1, 1]
    ]
    n = len(island)
    dx, dy좌표로 상하좌우 살피도록 한다. 12시부터 3시 6시 9시 순으로 가리킨다.(8방향이면 그 방향에 따라서 좌표를 넣으면 된다)
    dx = [-1, 0, 1, 0] # 위쪽은 -1, 아래는 1로 이동하며, 좌우는 0으로 행의 변화는 없다
    dy = [0, 1, 0, -1] # 왼쪽은 -1, 오른쪽은 1로 이동하며, 상하는 0으로 열의 변화는 없다.
    chArr = [[0] * n for _ in range(n)] # 방문을 체크할 배열
    chArr[0][0] = 1
    dist = [[0] * n for _ in range(n)] # 거리를 체크할 배열
    dQ = deque()
    dQ.append((0, 0)) # 출발점을 큐에 입력
    print('(6, 6) 이동 거리:', BFS(island))
출력:
(6, 6) 이동 거리: 14
-------
좌표보기:
for i in island:
    print(i)
print()
for i in dist:
    print(i)
출력 섬: 
[1, 1, 0, 1, 0, 1, 0]
[1, 1, 0, 0, 1, 1, 0]
[1, 1, 1, 0, 0, 1, 1]
[1, 1, 0, 0, 1, 1, 0]
[1, 0, 1, 1, 1, 0, 1]
[1, 1, 1, 0, 1, 1, 1]
[1, 0, 1, 1, 0, 1, 1]
출력 각 섬까지의 이동 거리:
[0, 1, 0, 0, 0, 15, 0]
[1, 2, 0, 0, 15, 14, 0]
[2, 3, 4, 0, 0, 13, 14]
[3, 4, 0, 0, 11, 12, 0]
[4, 0, 8, 9, 10, 0, 14]
[5, 6, 7, 0, 11, 12, 13]
[6, 0, 8, 9, 0, 13, 14]