백준 16720 (C++) BAZE RUNNER

최초 업로드: 2025-11-14 11:50:49

최근 수정 시간: 2025-11-14 11:50:49

게시자: rlatjwls3333

카테고리: 백준

# [Silver I] BAZE RUNNER

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

## 문제 설명

제2차 BAZE RUNNER(Bit MAZE RUNNER) 대회에 참가하게 된 세영이는 이번에야말로 우승하겠다고 다짐한다. BAZE RUNNER는 N×4짜리 미로에서 진행하고, 제일 왼쪽 위부터 시작해서 제일 오른쪽 아래로 도착하면 승리하는 게임이다. 미로의 제일 위 줄과 제일 아래 줄은 아무런 벽이 존재하지 않지만 그 사이에 있는 모든 줄들은 한 명이 지나갈만큼의 공간을 제외하고는 전부 벽으로 막혀 있다. 이제 참가자들은 단위 시간동안 다음의 두 가지 행동 중 하나를 할 수 있다.

이제 세영이가 우승하기 위해 도착까지 최소 몇 번의 행동을 해야 하는지 알려주는 프로그램을 작성하시오.

## 입력

첫 번째 줄에 미로의 크기 N(3 ≤ N ≤ 1000)이 주어진다.

다음 줄부터 N-2개의 줄에는 미로의 제일 위 줄과 제일 아래 줄을 제외한 각 줄의 정보가 주어진다.

줄은 총 0(길), 1(벽)로 이루어진 4개의 비트로 구성되어 있으며, 각 줄마다 오직 한 개의 길이 존재한다.

## 출력

첫 번째 줄에 세영이가 우승하기 위한 행동의 최솟값을 출력한다.

## 풀이
이동해야하는 횟수는 N+2회로 동일하고, 벽을 움직이는 최소 횟수만 구하면 된다.

벽을 구하는 최소 횟수는 길을 1, 2, 3, 4번째 줄로 일자길을 만드는데 필요한 행동 횟수 중 최소와 같다.

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

int pos[998];

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 for(int i=0;i<n-2;i++) {
 string s; cin >> s;
 pos[i] = s.find('0');
 }

int minDist=INT_MAX;
 for(int i=0;i<4;i++) {
 int dist=0;
 for(int j=0;j<n-2;j++) dist += min({abs(pos[j]-i), abs(pos[j]-i-4), abs(pos[j]-i+4)});
 minDist = min(minDist, dist);
 }
 cout << minDist+n+2;
}
```