[BOJ] 1261 알고스팟

DFS에서 백트랙킹하는 부분을 잘 생각해야 되는데 매번 고려하지 않아서 생각이상의 시간이 걸린다.

 

• 4방향을 모두 확인하면서 간다면 한 방향을 확인하고 그 방향으로는 더 이상 가면 안된다. 따라서 4방향을 모두 확인한 후에 false로 바꿔줘야 한다.
• row, col으로 하는게 안헷갈린다. x,y로 했다가 완전히 뒤죽 박죽이 되어있었다.

시간 초과가 뜨는 풀이이긴 하지만 DFS백트랙킹 잘 알아둬야 겠다.

#include <iostream>
#define MAX 100
using namespace std;
int N, M, next_col, next_row, res = INT32_MAX;
string MAP[MAX];
bool visit[MAX][MAX];
int d_row[4] = {-1, 0, 1, 0};
int d_col[4] = {0, 1, 0, -1};

bool possible(int row, int col){
    return ( col >= 0 && col < M ) && ( row >= 0 && row < N );
}
void input(){
    cin >> M >> N;

    for(int i = 0 ; i < N; i++)
        cin >> MAP[i];



}
void dfs(int row, int col, int cnt){
    //cout << row << " " << col << " " << MAP[row][col] << " " << cnt << endl;

    visit[row][col] = true;

    if(col == M - 1 && row == N - 1){
        res = min(cnt, res);
        visit[row][col] = false;

        return;
    }

    for(int i =0 ;i < 4; i++){
        next_col = col + d_col[i];
        next_row = row + d_row[i];

        if(possible(next_row, next_col) && !visit[next_row][next_col]){
            //visit[next_row][next_col] = true;

            if(MAP[next_row][next_col] == '1')
                dfs(next_row, next_col, cnt + 1);
            else
                dfs(next_row, next_col, cnt);

            //visit[next_row][next_col] = false;

        }


    }
    visit[row][col] = false;

}
int main() {
    input();
    //visit[0][0] = true;
    dfs(0,0,0);
    std::cout << res << std::endl;
    return 0;
}

 

 

deque로 풀어야 하는 문제이다.

 

 

• 최소의 벽을 부시고 목적지까지 가는것이 목표이기때문에 우선은 이동이 가능하다면 목적지에 가깝게 최대한 이동해야한다. 즉, 우선순위가 이동가능한 칸(0)을 가는 것이 높게된다.
• 이 문제는 단순한 BFS를 요구하는 문제가 아니다. 왜냐하면 BFS는 모든 간선의 가중치가 동일해야 한다는 전제 조건이 필요하기 때문이다.
• 그렇기 때문에 이 문제는 다음과 같은 방법들을 사용하여 해결할 수 있다.
  • 다익스트라 알고리즘
  • BFS 가중치가 0(우선순위가 높은)인 간선에 연결된 정점은 큐의 맨 뒤가 아닌 맨 앞에 넣는 방법
• 보통 이 문제는 다익스트라 알고리즘을 이용하여 푸는게 정석인거 같지만, 우선 이번 글에서는 deque를 이용하여 우선순위를 구분해 푸는 두번째 방법으로 풀어보겠다.

 

파랑 - 출발점, 빨강 - 도착점, 회색 - 벽, 하얀색 - 이동가능한 칸

 

 

1. 미로의 크기 및 미로 정보를 입력받는다.
2. 시작점 1,1에서부터 상하좌우로 탐색을 진행하며 deque를 이용하여 조건 1(맵을 벗어나지 않고, 갈 수있는 길(=0)이고, 방문하지 않았다면)이라면 deque의 맨앞에 삽입하고, 조건2(맵을 벗어나지 않고, 갈 수없는 길(=1)이고, 방문하지 않았다면)이라면 deque의 맨 뒤에 삽입한다.
3. deque의 앞에서부터 빼서 사용하므로 우선순위는 조건1 > 조건2가 된다.
4. 조건1일때는 visited 함수의 값은 default 값인 1로 유지가 되며, 조건2일때는 벽을 부시는 것이므로 +1씩 증가하게 된다.
5. 목적지 (N,M)에 도착할때까지 탐색을 이어나가고 도착한다면 bfs 함수에서 반환된 visited[N][M] - 1을 출력한다.

 

 

<iostream>
#include <deque>
#include <stdio.h>
#include <cstring> // memset
 
using namespace std;
 
#define MAX 100
 
struct component {
    int y, x;
};
 
// 우,하,좌,상
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
 
int M, N;
bool graph[MAX+1][MAX+1];
int visited[MAX+1][MAX+1];
 
bool is_inside(int ny, int nx){
    return (ny >= 1 && ny <= N && nx >= 1 && nx <= M);
}
 
int bfs() {
    deque<component> dq;
    dq.push_back({ 1, 1 });
    visited[1][1] = 1;
    while (!dq.empty()) {
        int y = dq.front().y;
        int x = dq.front().x;
        dq.pop_front();
 
        if (y == N && x == M) return visited[N][M] - 1;
 
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
 
            // 맵을 벗어나지 않고, 갈 수있는 길이고, 방문하지 않았다면
            if (is_inside(ny,nx) && graph[ny][nx] == 0 && visited[ny][nx] == 0) {
                dq.push_front({ ny,nx });
                visited[ny][nx] = visited[y][x];
            }
 
            // 맵을 벗어나지 않고, 갈 수없는 길이고, 방문하지 않았다면
            if (is_inside(ny, nx) && graph[ny][nx] == 1 && visited[ny][nx] == 0) {
                dq.push_back({ ny,nx });
                visited[ny][nx] = visited[y][x] + 1;
            }
        }
    }
}
 
int main() {
    /* 미로의 크기 및 미로 정보 입력*/
    scanf("%d %d", &M, &N);
    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;

 

 

 

 

 

 

[백준 1261, c++] 알고스팟(bfs,deque)