[백준 2206, c++] 벽 부수고 이동하기(bfs)

문제 번호

• 2206(https://www.acmicpc.net/problem/2206)

문제 및 입/출력

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

 

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

 

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

 

예제 입력1

6 4 0100 1110 1000 0000 0111 0000

예제 출력1

15

예제 입력2

4 4 0111 1111 1111 1110

예제 출력2

-1

 

문제 풀이

NxM의 맵에서 (1,1)에서 (N,M) 좌표까지 이동하는데 최소로 걸리는 시간을 구하는 문제이다. 벽이 존재한다면 단 한번 부실 수 있는 기회를 준다는 조건을 잘 고려하여 풀어야한다.

이를 풀기위해 BFS 알고리즘을 사용하였고, 내부에서 사용되는 visited 함수는 평소와 같은 이중배열 구조가 아닌 y,x 에다가 block의 뚫을 수 있는 여부까지 체크하려고 삼중 배열을 사용하였다.

queue 역시 queue<pair<pair<int, int>, int > > q; 구조를 선택했는데, {{y,x}, block}의 구조이다. 

 

• 맵의 크기 및 맵 정보(1: 벽, 0: 벽x) 입력
• 시작좌표(1,1)와 벽 뚫기가능 횟수 1을 queue에 넣고, bfs 탐색 시작.

1.  조건1(맵을 벗어나지 않는지?)을 체크하여 만족할 때,
2.  조건2(벽이면서 벽을 뚫을 기회가 있는지?)와 조건 3(벽이 아니고, 방문하지 않았다면)을 체크하여 만족할 때, visited 배열에 이동 횟수를 저장하고 해당 좌표와 block의 상태를 queue에 집어넣는다.
3. 1-2 과정을 queue가 비었거나, 현재 좌표 y, x가 목적지 좌표 N,M에 도달할때까지 탐색을 진행하는데, queue가 완전히 비어서 반복문을 나간 경우는 목적지에 도달하지 못했다는 말이 되므로 벽에 막혀서 진행을 못한 경우가 된다. 그래서 -1을 출력한다.
   반대로 목적지 좌표에 도달한 경우는 이동횟수를 출력한다. (시작점과 도착점 좌표까지 모두 포함하여 출력하므로 visited[y][x][block]을 그대로 출력한다.)

---

문제를 풀고 BOJ에서 검사를 받았을때, 120ms의 시간을 확인했다. 더 시간을 단축시킬 수 없을까하고 찾아보던중 가장 쉽게 고칠 수 있는 부분을 발견했다. 바로 scanf 부분이다. printf와 scanf는 많이 쓰면 쓸 수록 시스템을 느려지게 하는 원인들 중 하나이다. 

무작정 줄이는건 문제가 되지만, 문제를 해결하는데에 지장이 없이 줄일 수 있다면 줄이면 좋다는 것이다.

이 문제에서는 입력이 0100, 1110 ... 이런식으로 주어지는데 난 처음에 이 입력을 각각 int로 0, 1, 0 , 0 구분해서 담았다. 그렇기에 각각 입력을 담을때마다 scanf를 활용하게 되어 총 NxM 번의 scanf를 사용하게 되는것이 문제였다.

그래서 int 단위가 아닌 0100 자체를 문자로 보아서 string으로 char형 배열에 담음으로써 scanf를 총 N번으로 줄일 수 있었다. 그래서 N번의 scanf를 써서 코드를 실행시켜보니, 초기 120ms에서 68ms로 빨라진 것을 볼 수있었다.

 

공부를 하면서 이 외적으로 더 줄일 수 있는 부분이 무엇인지 생각하면서 공부를 해야겠다고 느꼈다.

소스 코드

#1. 그래프를 int형으로 선언하여 맵 정보를 받아올때,

#include <iostream>
#include <queue>
#include <stdio.h>
#include <stdlib.h>
 
using namespace std;
 
#define MAX 1000
 
typedef struct {
    int y, x;
}Dir;
 
Dir moveDir[4] = { {1,0},{0,1},{-1,0},{0,-1} };
 
int N, M;
bool graph[MAX + 1][MAX + 1];
int visited[MAX + 1][MAX + 1][2]; // y, x, block 뚫을수 있는 횟수
 
bool is_inside(int _ny, int _nx) {
    return (_ny >= 1 && _ny <= N && _nx >= 1 && _nx <= M);
}
 
int bfs() {
    queue<pair<pair<int, int>, int > > q;
    q.push({ {1,1} , 1}); // y, x, block 뚫을수 있는 횟수
    visited[1][1][1] = 1;
 
    while (!q.empty()) {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int block = q.front().second;
        q.pop();
 
        if (y == N && x == M) {
            return visited[y][x][block];
        }
 
        for (int i = 0; i < 4; i++) {
            int ny = y + moveDir[i].y;
            int nx = x + moveDir[i].x;
 
            // 맵을 벗어나지 않고,
            if (is_inside(ny, nx)) {
                // 갈 수없는 길(벽)이고, 벽을 아직 안뚫었을때
                if (graph[ny][nx] == 1 && block) {
                    visited[ny][nx][block - 1] = visited[y][x][block] + 1;
                    q.push({ { ny,nx }, block - 1 });
                }
                // 갈 수있는 길이고, 방문하지 않았다면
                if (graph[ny][nx] == 0 && visited[ny][nx][block] == 0) {
                    visited[ny][nx][block] = visited[y][x][block] + 1;
                    q.push({ { ny,nx }, block });
                }
            }
        }
    }
    // 목적지에 도착하지 못하고 탐색이 종료되었을때
    return -1;
}
 
int main() {
    /* 맵의 크기 및 맵 정보 입력 */
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            scanf("%1d", &graph[i][j]);
        }
    }
 
    /* bfs 탐색 진행 및 결과 출력 */
    printf("%d\n", bfs());
    return 0;
}