프로그래밍/알고리즘

BOJ 13903 · 출근

반응형


알고리즘 분류 : BFS  


출근하기 위해 필요한 최소 걸음을 구하는 문제다. BFS를 통해 최소 횟수를 구하면 된다. 첫 번째 줄부터 시작해서 마지막 줄에 도착하면 출근에 성공한 것이다. 마지막 줄에 도달하지 못하면 출근할 수 없다. 이동 방법이 정해져 있지 않으므로, 이 부분만 잘 구현하면 일반적인 BFS 문제와 비슷하다.


  • R*C 사이즈의 맵을 기준으로, 0번째 줄에서 출발하여 R-1번째 줄에 도착하면 출근이 가능한 것이다.
  • 0번째 줄에 있는 세로 블록(1)을 큐에 모두 집어넣는다.
  • 입력으로 주어지는 이동 규칙에 따라 이동을 한다. 가로 블록(0)으로는 이동할 수 없다.
  • R-1번째 줄에 도착하면 이동 횟수를 출력하고, 만약 도착할 수 없다면 -1을 출력한다.





C++ 소스코드


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

struct block {
    int x, y;
};

int r, c, n;
int a[1000][1000];
int dist[1000][1000];
int dx[10], dy[10];
queue<block> q;

void bfs() {
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y; q.pop();
        if (x == r-1) {
            printf("%d\n", dist[x][y]);
            return;
        }
        for (int i=0; i<n; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            if (dist[nx][ny] == -1 && a[nx][ny]) {
                q.push({nx, ny});
                dist[nx][ny] = dist[x][y]+1;
            }
        }
    }
    printf("-1\n");
}

int main() {
    scanf("%d %d", &r, &c);
    for (int i=0; i<r; i++) {
        for (int j=0; j<c; j++) {
            scanf("%d", &a[i][j]);
            dist[i][j] = -1;
        }
    }
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        scanf("%d %d", &dx[i], &dy[i]);
    }
    for (int i=0; i<c; i++) {
        if (a[0][i]) {
            q.push({0, i});
            dist[0][i] = 0;
        }
    }
    bfs();
    return 0;
}




Python 3 소스코드


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

def bfs():
    while q:
        x, y = q.popleft()
        if x == r-1:
            print(dist[x][y])
            return
        for k in range(n):
            nx, ny = x+dx[k], y+dy[k]
            if nx < 0 or nx >= r or ny < 0 or ny >= c:
                continue
            if dist[nx][ny] == -1 and a[nx][ny]:
                q.append((nx, ny))
                dist[nx][ny] = dist[x][y]+1
    print(-1)

r, c = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(r)]
dist = [[-1]*c for _ in range(r)]
n = int(input())
dx, dy = [0]*n, [0]*n
q = deque()
for i in range(n):
    dx[i], dy[i] = map(int, input().split())
for i in range(c):
    if a[0][i]:
        q.append((0, i))
        dist[0][i] = 0
bfs()




참고



반응형