백준 1952 - 달팽이2 [C/C++]

1952번: 달팽이2 (acmicpc.net)

문제 설명

예시 설명 및 입력과 출력

 

스스로 반성하게 된 문제..

 

브론즈 문제라고 얕보다가 아차 싶었던 문제이다.

 

이게 브론즈 문제라고?? 천천히 생각해보지 않으면 골드 문제보다도 버거울 수 있다.

 

물론 조건문 와다다닥 써서 해결하면 금방 풀리겠지만, 본인은 BFS처럼 풀려고 했기 때문에 시간이 좀 걸렸을 수 있다.

 

우선 이동 방향의 우선 순위를 보면, 오른쪽, 아래쪽, 왼쪽, 위쪽이고,

"이것이 반복된다"는 것을 인지해야 한다.

 

즉, 다 돌았다고 끝난게 아니고, 다시 오른쪽으로 돌아가 탐색해야 하는 것이다. 벽을 타고 움직이는 것이기 때문에 이전의 움직였던 방향을 저장해두었다가 그 방향 자체가 바뀌었다면 대각 화살표가 나타난 것이라고 생각해도 좋다.

 

대각 화살표가 나타난 분기점이 바로 "저 이동 방향의 우선 순위 리스트에서의 뽑혀야 할 이동 방향이 달라졌다"는 것을 의미한다.

 

코드를 살펴보며 이해해보도록 하자.

#include <iostream>
#include <queue>
#include <string.h>

using namespace std;

int m, n;
bool wall[101][101];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> m >> n;
    memset(wall, 0, sizeof(wall));
    int i=0;
    int mx=0;
    int my=0;
    int cnt = 1;
    int ans = 0;
    wall[0][0] = 1;
    while(1)
    {
        if(cnt==m*n)break;
        int next_x = mx+dx[i];
        int next_y = my+dy[i];
        if (wall[next_y][next_x] || next_y < 0 || next_y > m-1 || next_x < 0 || next_x > n-1){
            ans++;
            if(i==3)i=0;
            else i++;
        }
        else{
            cnt++;
            mx = next_x;
            my = next_y;
            wall[next_y][next_x] = 1;
        }
    }
    cout << ans << '\n';
    

    return 0;
}