반응형
알고리즘 분류 : 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()
참고
- 백준 온라인 저지 : BOJ 13903
반응형