백준 13903 (C++) 출근

최초 업로드: 2025-11-15 16:55:12

최근 수정 시간: 2025-11-15 16:55:12

게시자: rlatjwls3333

카테고리: 백준

# [Silver I] 출근

[문제 링크](https://www.acmicpc.net/problem/13903)

## 문제 설명

준규는 오랜만에 회사에 출근하려 한다. 준규는 수학을 엄청 좋아해서 항상 규칙을 정하는데, 강남역에서 내린 준규는 회사까지 가는 길에 깔려있는 보도블록을 보고 규칙을 정하기 시작했다.

<ol>
	<li>세로 블록만 밟는다. (시작은 첫 번째 row의 세로 블록 중 아무 곳에서나 가능하다.)</li>
	<li>특정 규칙(예를 들어 상하좌우, 체스의 나이트 이동 규칙 등)으로 이동한다.</li>
	<li>첫 번째 row에서 출발하여 마지막 row에 도착하면 출근에 성공한 것이다.</li>
	<li>마지막으로 준규는 걷는 것이 매우 귀찮아서 최소한의 걸음으로 출근을 하고 싶다.</li>
</ol>

<img alt="" src="https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/13903/2.png" style="float:right; height:89px; width:90px">위 보도블록 상태를 이용하여 간단한 예시를 들어보자. 1번 규칙으로 밟을 수 있는 블록은 세로 블록이며(색칠 된 블록), 이동 규칙이 오른쪽 이미지와 같다면, 준규는 회사로 가는 여러 경로 중 점선과 실선의 방법으로 출근을 할 수 있다. 실선은 세 걸음으로 출근이 가능한 반면 점선은 두 걸음에 출근이 가능하다.

수학을 좋아하지만 수학을 못하는 준규를 위해서 준규가 만든 규칙으로 출근을 할 수 있는지, 출근이 가능하다면 최소 몇 걸음에 출근이 가능한지 출력하는 프로그램을 작성하시오.

## 입력

첫 번째 줄에는 보도블록의 세로, 가로 R, C(1 ≤ R, C ≤ 1,000)크기가 주어진다. 다음 R개의 줄에는 C개의 문자로 이루어진 보도블록의 초기 상태가 주어진다. (가로 블록은 0로 표시되고, 세로 블록은 1로 표시된다.) 그 다음 줄에 이동 가능한 규칙의 개수 N(0 ≤ N ≤ 10)이 주어지고 그 다음 N개의 줄에 걸쳐 규칙 r(-R ≤ r ≤ R), c(-C ≤ c ≤ C)가 주어진다. 이 뜻은 현재 위치가 (0, 0) 일 때 (0+r, 0+c)로 이동 할 수 있음을 의미한다. ((0,0)왼쪽 위, (R – 1, C – 1)오른쪽 아래 블록이다.)

## 출력

준규가 출근을 하는데 최소 몇 번의 걸음을 걸어야 하는지 출력한다. 만약 출근할 수 없다면 -1을 출력한다.

## 풀이
이동 방향이 입력으로 주어지는 bfs 문제입니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

bool board[1000][1000];
int visited[1000][1000];

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int r, c; cin >> r >> c;
 for(int i=0;i<r;i++) for(int j=0;j<c;j++) cin >> board[i][j];

int n; cin >> n;
 vector<pair<int, int>> mv(n);
 for(int i=0;i<n;i++) cin >> mv[i].first >> mv[i].second;

queue<pair<int, int>> q;
 memset(visited, -1, sizeof visited);
 for(int i=0;i<c;i++) {
 if(board[0][i]) {
 q.push({0, i});
 visited[0][i]=0;
 }
 }
 while(!q.empty()) {
 auto [x, y] = q.front(); q.pop();
 if(x==r-1) {
 cout << visited[x][y];
 return 0;
 }
 for(int i=0;i<n;i++) {
 int nx = x+mv[i].first;
 int ny = y+mv[i].second;
 if(nx<0 || nx>=r || ny<0 || ny>=c || visited[nx][ny]!=-1 || !board[nx][ny]) continue;
 q.push({nx, ny});
 visited[nx][ny]=visited[x][y]+1;
 }
 }
 cout << -1;
}
```