꼭 알아야하는 코딩 테스트 유형 : 14) #BFS

• 이번에는 코딩 테스트에서 꼭 알아야하는 유형 중 하나인 BFS(Breadth-First Search)에 대해 알아보겠습니다. BFS는 그래프 탐색 알고리즘 중 하나로, 너비 우선으로 탐색을 수행하는 방법입니다. 이전 그래프 이론 및 탐색 포스팅에서 간략하게 설명하였는데, 이번 글에서는 BFS의 개념과 코딩 테스트에서 BFS 문제를 접했을 때 어떻게 접근해야 하는지에 대해 자세하게 설명하도록 하겠습니다.

 

BFS란?

 

• BFS는 그래프 탐색 방법 중 하나로, 시작 정점에서부터 인접한 정점들을 먼저 모두 방문한 후, 다음 단계의 인접 정점들을 차례대로 방문하는 방식입니다. 이러한 너비 우선 탐색은 큐(Queue) 자료구조를 활용하여 구현됩니다.
• BFS의 동작 원리는 다음과 같습니다.

 

1. 시작 정점을 큐에 넣고 방문 여부를 체크합니다.
2. 1) 큐가 비어있지 않은 동안 다음 과정을 반복합니다.
   2) 큐에서 정점을 하나 꺼내고 해당 정점과 인접한 모든 정점들 중 아직 방문하지 않은 정점들을 큐에 넣고 방문 여부를 체크합니다.
3. 큐가 비어있다면 모든 연결된 정점들을 탐색한 것입니다.

• BFS는 최단 경로 문제나 상태 공간 탐색 등 다양한 문제에 활용됩니다.

 

코딩 테스트에서의 BFS 문제 접근 전략

 

• 코딩 테스트에서의 BFS 문제는 보통 그래프 형태로 주어진 문제입니다. 예를 들어, 미로 찾기, 최단 경로 찾기, 연결된 섬 개수 세기 등 다양한 유형의 문제가 있습니다.
• BFS 문제를 해결하기 위해서는 다음과 같은 단계로 접근할 수 있습니다.

 

1. 그래프 구성: 주어진 입력으로 그래프를 구성합니다. 일반적으로 인덱스나 좌표 형태로 노드와 간선 정보를 저장하게 됩니다.
2. 큐 초기화: 시작 노드(시작 위치)를 큐에 추가하고 방문 여부를 체크하기 위한 배열이나 집합 등도 초기화합니다.
3. 1) 큐 반복: 크기가 0이 될 때까지 반복하여 아래 과정을 수행합니다.
   2) 큐에서 노드(위치)를 하나 꺼내고 해당 노드와 연결된 인접 노드들 중 아직 방문하지 않은 노드들만 큐에 추가하고 방문 여부 체크합니다.
4. 원하는 결과 도출: 필요에 따라 각 단계마다 웹한다던지 조건 검사 등 결과값 도출 작업도 진행할 수 있습니다.

 

• 이러한 접근법으로 주어진 그래프 혹은 상황 속에서 필요한 정보 및 결과값을 찾아낼 수 있습니다.

 

2583번: 영역 구하기

  문제  

 

• 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.
• 예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

• <그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.
• M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

 

  해결 방법  
 

• 이 문제는 주어진 사각형 안에서 각각의 분리된 공간의 크기를 찾는 문제입니다.
• 문제의 접근 방식은 다음과 같습니다.

 

1. 그래프 생성: 주어진 입력 정보를 바탕으로 그래프를 생성합니다.
2. BFS 실행: 모든 정점에 대해 아직 방문하지 않았다면 BFS를 실행하여 각각의 분리된 공간을 찾습니다.
3. 영역 크기 계산: 각 BFS 실행마다 탐색한 정점들의 개수가 해당 영역의 크기가 됩니다.

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

M, N, K = map(int, input().split())
board = [[0] * N for _ in range(M)]
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

for _ in range(K):
    x1, y1, x2, y2 = map(int,input().split())
    for i in range(y1, y2):
        for j in range(x1, x2):
            board[i][j] = 1

def bfs(x, y):
    q = deque()
    q.append((x, y))
    board[x][y] = 1
    cnt = 1

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < M and 0 <= ny < N and board[nx][ny] == 0:
                q.append((nx, ny))
                board[nx][ny] = 1
                cnt += 1
    return cnt

result = []
for i in range(M):
    for j in range(N):
        if board[i][j] == 0:
            result.append(bfs(i, j))

print(len(result))
print(*sorted(result))

 
 

13913번: 숨바꼭질 4

  문제  

 

• 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
• 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

  해결 방법  

 

• 이 문제는 시작 위치에서 목표 위치까지 가장 빠르게 이동하는 방법과 그 경로를 찾는 문제입니다.
• 문제의 접근 방식은 다음과 같습니다:

 

1. 그래프 생성: 이 문제에서 그래프는 1차원 배열로, 인덱스가 위치를 나타내며 값은 해당 위치에 도달하기까지 걸린 최소 시간입니다.
2. BFS 실행: 시작 위치에서 BFS를 실행하여 모든 가능한 이동 경로를 탐색합니다.
3. 경로 추적: 목표 위치에 도달한 후 역으로 경로를 추적하여 최단 경로를 찾습니다.

from collections import deque

def bfs():
    q = deque([N])
    while q:
        now_pos = q.popleft()
        if now_pos == K:
            print(time[now_pos])
            p = []
            while now_pos != N:
                p.append(now_pos)
                now_pos = path[now_pos]
            p.append(N)
            p.reverse()
            print(*p)
            return
        for next_pos in (now_pos-1, now_pos+1, now_pos*2):
            if 0 <= next_pos < MAX and not time[next_pos]:
                q.append(next_pos)
                time[next_pos] = time[now_pos] + 1
                path[next_pos] = now_pos

N,K = map(int,input().split())
MAX = 100001
time = [0] * MAX
path = [0] * MAX

bfs()

 

• BFS는 그래프를 너비 우선으로 탐색하는 기법으로, 다양한 문제 상황에서 활용할 수 있습니다. 최단 경로 찾기, 연결 요소 찾기 등 많은 유형의 문제에서 BFS를 이용하면 효율적이고 명확한 해답을 도출할 수 있습니다.