[BOJ/백준] 1261 알고스팟

● [문제번호 1261] 알고스팟

https://www.acmicpc.net/problem/1261

1261번: 알고스팟

 

● 알아야 할 것

: pair 자료구조와 메소드

: BFS

 

● 풀이 과정

: 최소 이동 횟수를 구하는 것이 아닌

출발점에서 도착점까지 꼬불꼬불 돌아서 가더라도

부순 문의 수가 최소가 되어야한다.

그래서 BFS로 구현할 때 중간에 멈추는 조건을 넣지 않았다.

 

: BFS로 구현하면서

현재위치에서 다음위치로 갈 때,

1. 다음위치가 미로를 벗어나면 continue

 

2. 다음위치가 방문한 적 있는 경우

2-1. 빈 방인 경우, {현재위치 부순 문의 수} < {다음위치 부순 문의 수} → 갱신

2-2. 벽인 경우, {현재위치 부순 문의 수 + 1} < {다음위치 부순 문의 수} → 갱신

 

3. 다음위치가 방문한 적 없는 경우

3-1. 빈 방인 경우, {현재위치 부순 문의 수}로 입력

3-2. 벽인 경우, {현재위치 부순 문의 수 + 1} 로 입력

 

: 빈 방과 구분하기 위해

출발방의 값을 1로 두었다.

따라서 마지막에 출력할 때는 -1 을 해야한다.

 

● 주의 할 것

: 초기 입력값 N, M이

행(세로), 열(가로)이 아니라

열(가로), 행(세로) 이다.

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// controlX : 미로에서 움직이기 위한 상, 하, 좌, 우
// controlY : 미로에서 움직이기 위한 상, 하, 좌, 우
// maze : 미로 입력
// visited : 방문기록 (값 : 해당 좌표까지 오기위한 부순 문의 수)
int controlX[4] = {-1, 1, 0, 0};
int controlY[4] = {0, 0, -1, 1};
int maze[101][101];
int visited[101][101];
int N, M;

// 너비 우선 탐색
void bfs()
{
    // 좌료를 이용하여 탐색하므로 pair 자료구조 이용
    queue<pair<int, int>> q;
    
    // 출발점
    // 방문 여부를 구분하기 위해 출발점의 부순 벽의 수 1로 설정
    visited[1][1] = 1;
    q.push(pair<int, int>(1, 1));
    
    while(!q.empty())
    {
        int fromX = q.front().first;
        int fromY = q.front().second;
        
        q.pop();
        
        // 상 하 좌 우
        for(int i = 0; i < 4; i++)
        {
            int toX = fromX + controlX[i];
            int toY = fromY + controlY[i];
            
            // 미로의 X축을 벗어난 경우
            if(toX < 1 || M < toX)
                continue;
            // 미로의 Y축을 벗어난 경우
            else if(toY < 1 || N < toY)
                continue;
            
            // 방문한 적 있는 경우
            if(visited[toX][toY])
            {
                // 빈 방인 경우
                if(maze[toX][toY] == 0)
                {
                    // 최소로 부순 벽의 수
                    if(visited[fromX][fromY] < visited[toX][toY])
                    {
                        visited[toX][toY] = visited[fromX][fromY];
                        q.push(pair<int, int>(toX, toY));
                    }
                }
                // 벽인 경우
                else if(maze[toX][toY] == 1)
                {
                    // 최소로 부순 벽의 수
                    if(visited[fromX][fromY] + 1 < visited[toX][toY])
                    {
                        visited[toX][toY] = visited[fromX][fromY] + 1;
                        q.push(pair<int, int>(toX, toY));
                    }
                }
            }
            // 방문한 적 없는 경우
            else
            {
                // 빈 방의 경우
                if(maze[toX][toY] == 0)
                {
                    visited[toX][toY] = visited[fromX][fromY];
                    q.push(pair<int, int>(toX, toY));
                }
                // 벽의 경우
                else if(maze[toX][toY] == 1)
                {
                    visited[toX][toY] = visited[fromX][fromY] + 1;
                    q.push(pair<int, int>(toX, toY));
                }
            }
        }
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> M;
    
    // N : 가로 (X축)
    // M : 세로 (Y축)
    for(int m = 1; m <= M; m++)
    {
        for(int n = 1; n <= N; n++)
        {
            // 숫자 1개씩 받아야 하므로
            char input;
            cin >> input;
            
            maze[m][n] = input - '0';
        }
    }
    
    bfs();
    
    // 출발점의 visited값을 1로 설정했기에 출력시 1을 뺀다
    cout << visited[M][N] - 1;
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [610 - BFS] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	1697	숨바꼭질	https://pirateturtle.tistory.com/283
2	13913	숨바꼭질 4	https://pirateturtle.tistory.com/284
3	14226	이모티콘	https://pirateturtle.tistory.com/285
4	13549	숨바꼭질 3	https://pirateturtle.tistory.com/286
5	1261	알고스팟	https://pirateturtle.tistory.com/287