본문 바로가기

Programming/BOJ

BOJ 2146 · 다리 만들기


알고리즘 분류 : BFS


BFS(또는 DFS)를 통해 맵 전체를 탐색하면서 최단 거리를 구하는 문제이다. BOJ 1261번 '알고스팟'과 비슷한 문제이다.

Queue를 2개 이용하거나, Deque을 이용하여 해결할 수 있다.


  • Deque을 선언하고, 시작점을 육지(1)로 하여 한 군데의 위치를 Deque에 넣어둔다.
  • BFS 탐색을 하면서 섬과 섬 사이의 거리가 가장 짧은 곳을 정답으로 낸다.
  • 현재 위치가 육지(1)이고, 다음 위치도 육지(1)라면, 이동 거리를 업데이트하지 않는다.
  • 현재 위치가 육지(1)이고, 다음 위치가 바다(0)라면, 이동 거리를 1로 바꾼다.
  • 현재 위치가 바다(0)이고, 다음 위치도 바다(0)라면, 이동 거리를 1만큼 증가시킨다.
  • 현재 위치가 바다(0)이고, 다음 위치가 육지(1)라면, 현재 이동 거리를 정답 후보에 넣는다.
  • 정답 후보는 별도의 변수를 통해 현재 이동 거리와 이전 이동 거리를 비교하면서, 더 작은 값으로 업데이트하면 된다.




C++ 소스코드


#include <cstdio>
#include <deque>
using namespace std;

struct bridge {
    int x, y, d;
};

int n;
int a[101][101];
bool check[101][101];
deque<bridge> q;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int bfs() {
   int ans = 1e9;
   while (!q.empty()) {
       int x = q.front().x, y = q.front().y, d = q.front().d;
       q.pop_front();
       for (int i=0; i<4; i++) {
           int nx = x+dx[i], ny = y+dy[i];
           if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
           if (check[nx][ny]) continue;
           if (a[nx][ny] == 1) {
               q.push_front({nx, ny, d});
               if (a[x][y] == 0 && ans > d) ans = d;
           } else {
               if (a[x][y] == 0) q.push_back({nx, ny, d+1});
               else q.push_back({nx, ny, 1});
           }
           check[nx][ny] = true;
       }
   }
   return ans; 
}

int main() {
    scanf("%d", &n);
    bool init = true;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            scanf("%d", &a[i][j]);
            if (init && a[i][j] == 1) {
                init = false;
                q.push_front({i, j, 0});
                check[i][j] = true;
            }
        }
    }
    printf("%d\n", bfs());
    return 0;
}




Python 3 소스코드


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

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
check = [[False]*n for _ in range(n)]
q = deque()
dx = (-1, 0, 1, 0)
dy = (0, 1, 0, -1)

def bfs():
    ans = 1e9
    while q:
        x, y, d = q.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if check[nx][ny] is True:
                continue
            if a[nx][ny] == 1:
                q.appendleft((nx, ny, d))
                if a[x][y] == 0 and ans > d:
                    ans = d
            else:
                if a[x][y] == 1:
                    q.append((nx, ny, 1))
                else:
                    q.append((nx, ny, d+1))
            check[nx][ny] = True
    return ans

def init():
    for i in range(n):
        for j in range(n):
            if init and a[i][j] == 1:
                q.append((i, j, 0))
                check[i][j] = True
                return

init()
print(bfs())




참고



태그