백준 34326 (C++) How to escape the maze

최초 업로드: 2025-10-27 03:39:50

최근 수정 시간: 2025-10-27 03:39:50

게시자: rlatjwls3333

카테고리: 백준

# [Silver II] How to escape the maze

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

## 문제 설명

우연이는 수업 시간에 멍하니 있다가, 현실 세계에서 미로에 갇히면 어떻게 해야 확실하게 탈출할 수 있을지 문득 궁금해졌다.

수업이 끝난 후, 그는 그 방법을 인터넷에서 찾아보다가 좌수법이라는 기법을 알게 되었다. 깨달음을 얻은 우연이는 옆에 앉아 있던 보경이에게 "좌수법을 쓰면 미로를 무조건 탈출할 수 있다."라고 말했다. 하지만 보경이는 이미 그 방법을 알고 있었고, 직접 사용해 본 결과 좌수법보다 우수법이 더 낫다고 주장했다.

$N$개의 행과 $M$개의 열로 이루어진 격자 모양의 미로가 주어진다. 미로의 칸은 빈칸, 벽, 입구, 출구 중 하나의 상태를 갖는다. 입구에서의 시선은 가장 가까운 빈칸을 향한다.

좌수법과 우수법은 다음의 세 가지 행동을 조합하여 수행할 수 있다.

좌수법의 경우 아래 의사 코드를 따라 움직인다.

<pre>while 도착 지점에 도착하지 않음 :
 좌회전한다
 while 전진 할 수 없음 :
 우회전한다
 전진한다</pre>

우수법의 경우 아래 의사 코드를 따라 움직인다.

<pre>while 도착 지점에 도착하지 않음 :
 우회전한다
 while 전진 할 수 없음 :
 좌회전한다
 전진한다</pre>

보경이의 자신만만한 말투에 괜히 기분이 상한 우연이는 좌수법이 더 우수한 방법이라며 맞섰고, 결국 둘은 어떤 방법이 더 좋은지를 직접 프로그램으로 구현해 확인해 보기로 했다.

## 입력

첫째 줄에 두 정수 $N$, $M$가 공백으로 구분되어 주어진다. $(3 \le N, M \le 1\,000)$

이어서 $N$개의 줄에 걸쳐 길이 $M$의 문자열이 주어진다. $i+1$번째 줄의 $j$번째 문자는 위에서 $i$번째 행과 왼쪽에서 $j$번째 열이 교차하는 칸의 상태를 나타낸다.

<code>.</code>은 빈칸, <code>*</code>은 벽, <code>S</code>는 입구, <code>E</code>는 출구를 의미한다.

두 지점 <code>S</code>와 <code>E</code>는 입력 전체에 각각 한 번씩 등장하고, 좌우상하 어떤 방향으로도 인접하지 않으며, 미로의 가장자리에 위치한다. 가장자리에 빈칸 <code>.</code>은 위치하지 않는다.

탈출이 가능한 경우만 주어진다.

## 출력

좌수법을 사용할 경우 먼저 탈출이 가능하다면 <code>LEFT IS BEST</code>를, 우수법을 사용할 경우 먼저 탈출이 가능하다면 <code>RIGHT IS BEST</code>를 출력한다.

어느 방법을 써도 동일한 최단 시간에 탈출이 가능할 경우 <code>SAME</code>을 출력한다.

## 풀이
지문에서 나온 그대로 구현하면 됩니다. dir 변수를 두고 풀면 쉽게 구현할 수 있습니다.

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

int n, m;
string board[1000];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int left(int x, int y, int dir) {
    int cnt=0;
    while(board[x][y]!='E') {
        dir = (dir+3)%4;
        while(board[x+dx[dir]][y+dy[dir]]=='*') dir = (dir+1)%4;
        x += dx[dir];
        y += dy[dir];
        cnt++;
    }
    return cnt;
}

int right(int x, int y, int dir) {
    int cnt=0;
    while(board[x][y]!='E') {
        dir = (dir+1)%4;
        while(board[x+dx[dir]][y+dy[dir]]=='*') dir = (dir+3)%4;
        x += dx[dir];
        y += dy[dir];
        cnt++;
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;

int x, y;
 for(int i=0;i<n;i++) {
 cin >> board[i];
 for(int j=0;j<m;j++) {
 if(board[i][j]=='S') x=i, y=j;
 }
 }
 int dir;
 if(y==0) dir=0;
 else if(x==0) dir=1;
 else if(y==m-1) dir=2;
 else dir=3;

int l = left(x, y, dir);
 int r = right(x, y, dir);
 if(l==r) cout << "SAME";
 else if(l<r) cout << "LEFT IS BEST";
 else cout << "RIGHT IS BEST";
}
```