fragment-header
fragment-markdown
홈
로그인
로그아웃
내 블로그
설정
로그인
백준 13903 (C++) 출근
최초 업로드: 2025-11-15 16:55:12
최근 수정 시간: 2025-11-15 16:55:12
게시자: rlatjwls3333
카테고리: 백준
조회수: 6
# [Silver I] 출근 [문제 링크](https://www.acmicpc.net/problem/13903) ## 문제 설명 <p>준규는 오랜만에 회사에 출근하려 한다. 준규는 수학을 엄청 좋아해서 항상 규칙을 정하는데, 강남역에서 내린 준규는 회사까지 가는 길에 깔려있는 보도블록을 보고 규칙을 정하기 시작했다.</p> <ol> <li>세로 블록만 밟는다. (시작은 첫 번째 row의 세로 블록 중 아무 곳에서나 가능하다.)</li> <li>특정 규칙(예를 들어 상하좌우, 체스의 나이트 이동 규칙 등)으로 이동한다.</li> <li>첫 번째 row에서 출발하여 마지막 row에 도착하면 출근에 성공한 것이다.</li> <li>마지막으로 준규는 걷는 것이 매우 귀찮아서 최소한의 걸음으로 출근을 하고 싶다.</li> </ol> <p style="text-align:center"><img alt="" src="https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/13903/1.png" style="height:235px; width:405px"></p> <p><img alt="" src="https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/13903/2.png" style="float:right; height:89px; width:90px">위 보도블록 상태를 이용하여 간단한 예시를 들어보자. 1번 규칙으로 밟을 수 있는 블록은 세로 블록이며(색칠 된 블록), 이동 규칙이 오른쪽 이미지와 같다면, 준규는 회사로 가는 여러 경로 중 점선과 실선의 방법으로 출근을 할 수 있다. 실선은 세 걸음으로 출근이 가능한 반면 점선은 두 걸음에 출근이 가능하다.</p> <p>수학을 좋아하지만 수학을 못하는 준규를 위해서 준규가 만든 규칙으로 출근을 할 수 있는지, 출근이 가능하다면 최소 몇 걸음에 출근이 가능한지 출력하는 프로그램을 작성하시오.</p> ## 입력 <p>첫 번째 줄에는 보도블록의 세로, 가로 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)오른쪽 아래 블록이다.)</p> ## 출력 <p>준규가 출근을 하는데 최소 몇 번의 걸음을 걸어야 하는지 출력한다. 만약 출근할 수 없다면 -1을 출력한다.</p> ## 풀이 이동 방향이 입력으로 주어지는 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; } ```