1261. 알고스팟

블로그 하고는 처음으로 푸는 백준 문제다. 오랜만에 풀었더니 인풋 방법이 아예 삼성과 달라서 버벅 버벅...

인풋 하는데 조금 오래 걸렸다.

문제부터 보자

문제

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.

벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.

만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는 Baekjoon Online Judge에 수록되어 있기 때문에, sudo를 사용할 수 없다.

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.

(1, 1)과 (N, M)은 항상 뚫려있다.

출력

첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

문제는 이렇다. N*M 행렬이 주어지고 1,1에서 N,M 까지 도달하는데 방문하는 최소한의 1의 개수를 출력하는 문제다.

처음에는 아무 생각 없이 DFS로 풀어야지 했는데 막상 구현하니 6*6에서도 시간이 꽤 걸려 BFS로 풀었다.

DFS는 최소 길 찾는데 쓰면 안된다는걸 다시 생각나게 하는 계기였다.

알고리즘 생각은

1.각 거리를 MAX로 설정해 놓고 1,1의 거리를 0으로 설정.

2. 4방향 탐색을 하면서 1이면 거리를 +, 0이면 거리 그대로, 가는 곳의 거리와 현재 거리를 비교해서 갱신

3. M,N 출력

BFS 코드를 보자

#include <iostream>
#include <queue>
using namespace std;
 
int MAP[101][101], moveX[]={-1,0,1,0}, moveY[]={0,1,0,-1}, dist[101][101];
int cnt,N,M;
void bfs()
{
    queue<pair<int, int> > q;
    q.push(make_pair(1,1));
    dist[1][1] = 0;
    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int mx = x + moveX[i];
            int my = y + moveY[i];
            if(mx<1||my<1||mx>M||my>N) continue;
            if(MAP[mx][my]==1)
            {
                if(dist[mx][my]>dist[x][y]+1)
                {
                    dist[mx][my]=dist[x][y]+1;
                    q.push(make_pair(mx,my));
                }
            }
            else{
                if(dist[mx][my] > dist[x][y])
                {
                    dist[mx][my] = dist[x][y];
                    q.push(make_pair(mx,my));
                }
            }
        }
    }
 
}
int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>N>>M;
    cnt = 99999999;
    for (int i = 1; i <= M; i++)
    {
        string Inp;
        cin >> Inp;
        for (int j = 1; j <= Inp.length(); j++)
        {
            MAP[i][j] = Inp[j-1] - '0';
            dist[i][j] = 99999999;
        }
    }
    bfs();
    cout<<dist[M][N]<<'\n';
    return 0;
}
 

dn

+++++

멍청하게 처음 짠 DFS

#include <iostream>
#include <string.h>
using namespace std;
 
int MAP[101][101], moveX[]={-1,0,1,0}, moveY[]={0,1,0,-1};
bool check[101][101];
int cnt,N,M;
void dfs(int x, int y, int dep)
{
    if (x==M&&y==N)
    {
        if (cnt > dep)
        {
            cnt = dep;
            return;
        }
    }
    for(int i=0;i<4;i++)
    {
        int mx = x + moveX[i];
        int my = y + moveY[i];
        if(mx<1||my<1||mx>M||my>N||check[mx][my]) continue;
        if (MAP[mx][my] == 1)
        {
            check[mx][my] = true;
            dfs(mx, my, dep + 1);
            check[mx][my] = false;
        }
 
        else
        {
            check[mx][my] = true;
            dfs(mx, my, dep);
            check[mx][my] = false;
        }
 
    }
}
int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>N>>M;
    cnt = 99999;
    for (int i = 1; i <= M; i++)
    {
        string Inp;
        cin >> Inp;
        for (int j = 1; j <= Inp.length(); j++)
        {
            MAP[i][j] = Inp[j-1] - '0';
        }
    }
 
    dfs(1,1,0);
    cout<<cnt<<'\n';
    return 0;
}
 

아 그리고 또 백준 제출 하면서 생각 났는데 

queue<pair<int, int> > q를 할 때 >>들의 사이를 띄어쓰기 해야한다. 하지 않으면 IDE에서는 돌아가도 백준에서는 컴파일 에러가 난다.