1261 / 알고스팟

알고스팟 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	6660	2539	1668	37.987%

문제

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 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)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

---

생각보다 빨리 풀어버린 문제.

여러가지 시도를 해봤다.

1. 그냥 BFS로 풀어봐야지 했다가 메모리 초과. (N,M)으로 가는게 목표니까 오른쪽이랑 아래로만 가면 되지 않을까?

2. 보통 메모리 초과는 중복된 값들이 들어가는 경우기 때문. 가만히 생각해보니 →↓로 갔을때랑 ↓→ 로 갔을때랑 중복 방문이 됨.

3. 중복방문 방지하고자 check배열을 만들었고, 그 배열을 MAX값으로 전부 초기화.

 - 움직일 때, 벽을 뿌수고, next_cnt를 증가시킨다.

  - next_cnt값이 check배열에 기록된 값보다 큰가?

   - yes : 무시

   - no : check배열에 next_cnt값을 갱신하고, 큐에 넣어준다.

4. 3번으로 그대로 했는데 메모리 초과는 해결됐으나, 이번엔 틀렸다고 뜸.

5. 문제 다시 읽어봄. 상, 하, 좌, 우로 움직이라고 나와있음. 아! 문제에서 시키는대로 해야되지 참. 그리고 방향 두개 더 추가.

6. 딩동댕

[code]

#include<iostream>
#include<queue>
#define P pair<int,int>
#define PI pair<P,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
 
int N, M, map[101][101], xx[] = { 1,0,-1,0 }, yy[] = { 0,1,0,-1 }, check[101][101];
char temp[101];
 
int bfs();
 
int main() {
 
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    cin >> N >> M;
 
    for (int i = 0; i < M; i++) {
        cin >> temp;
        for (int j = 0; j < N; j++) {
            map[i][j] = temp[j] - '0';
            check[i][j] = TMP_MAX;
        }
    }
 
    cout << bfs() << endl;
 
    return 0;
}
 
int bfs() {
    queue<PI> Q;
    Q.push(mp(mp(0, 0), 0));
 
    int _min = TMP_MAX;
 
    while (!Q.empty()) {
        int cx = Q.front().first.first, cy = Q.front().first.second, cnt = Q.front().second;
        Q.pop();
 
        if(cx == M-1 && cy == N-1) _min = _min > cnt ? cnt : _min;
 
        for (int i = 0; i < 4; i++) {
            int nx = cx + xx[i], ny = cy + yy[i], next_cnt = cnt;
            if (nx < 0 || ny < 0 || nx > M - 1 || ny > N - 1) continue;
            if (map[nx][ny] == 1) next_cnt++;
 
            if (check[nx][ny] > next_cnt) {
                check[nx][ny] = next_cnt;
                Q.push(mp(mp(nx, ny), next_cnt));
            }
        }
    }
 
    return _min;
}

여담) 다른 사람들 전부 다익스트라로 짰다는데... 이게 다익스트라랑 비슷한건지는 모르겠으나 다익스트라좀 다시 공부해야겠다.