Code and Crescendo raccoon

백준 2206번 문제입니다.

문제

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

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

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

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

입력

출력

알고리즘 아이디어

1. 벽을 뚫을 수 있는지 아닌지를 계속 체크해야 한다. (tuple 이용)

2. 최단거리를 구해야 하므로 BFS를 사용한다.

코드

#include <iostream>
#include <queue>
#include <tuple>
#include <vector>

using namespace std;

int N, M;
vector<vector<int>> graph;
vector<vector<vector<int>>> visited;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void BFS() {

    queue<tuple<int, int, int>> q;  // (x, y, 벽을 부순 상태(0 또는 1))
    q.push({0, 0, 1});
    visited[0][0][1] = 1; // 시작점 방문 처리 (벽을 부수지 않음)

    while (!q.empty()) {
        
        int x = get<0>(q.front());
        int y = get<1>(q.front());
        int broken = get<2>(q.front());  // 벽을 부쉈는지 여부 (1: 부수지 않음, 0: 부숨)
        q.pop();

        // 도착점에 도달한 경우
        if (x == M - 1 && y == N - 1) {

            cout << visited[y][x][broken] << "\n";
            return;
        }

        for (int i = 0; i < 4; i++) {

            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
                
                // 벽이 없는 경우
                if (graph[ny][nx] == 0 && visited[ny][nx][broken] == 0) {

                    visited[ny][nx][broken] = visited[y][x][broken] + 1;
                    q.push({nx, ny, broken});
                }

                // 벽이 있는 경우, 벽을 한 번도 부수지 않았을 때만 벽을 부수고 이동 가능
                else if (graph[ny][nx] == 1 && broken == 1 && visited[ny][nx][1] == 0) {

                    visited[ny][nx][0] = visited[y][x][broken] + 1;
                    q.push({nx, ny, 0});  // 벽을 부순 상태로 큐에 추가
                }
            }
        }
    }

    // 도착하지 못했을 때
    cout << -1 << "\n";
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;

    graph.resize(N, vector<int>(M));
    visited.resize(N, vector<vector<int>>(M, vector<int>(2, 0)));  // 2차원 배열에 벽을 부순 여부 추가

    for (int i = 0; i < N; i++) {

        string row;
        cin >> row;
        for (int j = 0; j < M; j++) {

            graph[i][j] = row[j] - '0';
        }
    }

    BFS();

    return 0;
}

혹시라도 틀린 내용이 있다면 댓글로 알려주시면 감사하겠습니다!!

백준 2468 입니다.

문제

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

알고리즘 아이디어

1. 모든 노드를 탐색하는 대신 침수된 노드를 만나면 탐색 종료를 해야한다.

2. 침수 안된 영역를 찾는데 알고리즘이 필요하고, 안 가본 노드 중 침수 안된 시작 노드를 찾는 과정 크게 2개로 나뉜다.

3. 침수 안된 시작 노드는 2중 반복문을 사용하고, 침수 안된 영역을 찾는데는 BFS를 사용한다.

코드

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>

using namespace std;

int N;

vector<vector<int>> city;
vector<vector<bool>> visited;

int BFS(int check);
void counting(int x, int y, int check);

int BFS(int check) {

    int area = 0;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(!visited[i][j] && city[i][j] > check) {
                counting(j, i, check);
                area++;
            }
        }
    }
    return area;
}

void counting(int x, int y, int check) {
    // 방향 이동 (상, 하, 좌, 우)
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};

    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    visited[y][x] = true;  // 시작점을 방문 처리

    while(!q.empty()) {

        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();

        // 상하좌우 네 방향 탐색
        for(int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];

            // 범위를 벗어나지 않고, 방문하지 않았으며, 물에 잠기지 않은 영역일 때
            if(nx >= 0 && nx < N && ny >= 0 && ny < N) {
                if(!visited[ny][nx] && city[ny][nx] > check) {
                    visited[ny][nx] = true;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int maxFlood = 0, minFlood = INT16_MAX, result = 1;

    cin >> N;

    city.resize(N, vector<int> (N, 0));
    visited.resize(N, vector<bool> (N, false));

    for(int i = 0; i <  N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> city[j][i];
            maxFlood = max(maxFlood, city[j][i]);
            minFlood = min(minFlood, city[j][i]);
        }
    }

    for(int i = minFlood; i < maxFlood; i++){
        fill(visited.begin(), visited.end(), vector<bool>(N, false));  // 방문 배열 초기화
        result = max(result, BFS(i));
    }

    cout << result << "\n";

    return 0;
}

혹시라도 틀린 내용이 있다면 댓글로 알려주시면 감사하겠습니다!!

백준 1697번 입니다.

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

int BFS(int index, int focus);

int BFS(int index, int focus) {

    vector<bool> visited(100001, false);
    
    // 위치와 이동 시간을 저장하는 큐. 큐의 각 요소는 (위치, 이동 횟수)를 저장.
    queue<pair<int, int>> q;
    q.push(make_pair(index, 0));

    while(!q.empty()) {

        int position = q.front().first;
        int count = q.front().second;
        q.pop();
		
        // 현재 위치가 목표 위치와 같으면, 이동 횟수를 반환
        if (position == focus) {
            return count;
        }

        if (position - 1 >= 0 && !visited[position - 1]) {
            visited[position - 1] = true;
            q.push(make_pair(position - 1, count + 1));
        } if (position + 1 <= 100000 && !visited[position + 1]) {
            visited[position + 1] = true;
            q.push(make_pair(position + 1, count + 1));
        } if (position * 2 <= 100000 && !visited[position * 2]) {
            visited[position * 2] = true;
            q.push(make_pair(position * 2, count + 1));
        }
    }
    return -1;
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N = 0, K = 0;

    cin >> N >> K;

    vector<vector<int>> graph;


    cout << BFS(N, K) << '\n';

    return 0;
}

혹시라도 틀린 내용이 있다면 댓글로 알려주시면 감사하겠습니다!!

너비 우선 탐색이란?

BFS(Breadth First Search) 알고리즘이란 그래프에서 모든 노드를 탐색하는 2가지 방법 중 인접한 노드를 우선으로 탐색하는 방법이다.

여기서 인접한 노드라는 것을 이해할려면 그래프에 대해서 알고 있어야 한다.

그래프(Graph)란 노드(Node)와 간선(Edge)로 이루어진 자료구조를 의미한다.

탐색을 시작할 시작 노드가 결정되면, 시작 노드로부터 한번에 갈 수 있는 노드가 정해져 있다. 이런 노드들을 인접한 노드라고 한다.

즉, 시작 노드에서 바로 갈 수 있는 노드들을 먼저 탐색하고, 그 노드들을 모두 탐색 한 후, 다음 노드로 넘어가게 되는 방식이다.

BFS와 Queue

BFS는 인접 노드를 먼저 탐색해야 하기 때문에 FIFO(First In First Out) 자료구조인 Queue 자료구조를 사용하게된다.

인접 노드를 Queue에 넣어놓고, Queue에서 빼서 다시 탐색하는 과정을 구현하면 되는 것이다.

BFS 구현

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

int x, y;
vector<vector<int>> graph;
vector<vector<bool>> visited;

int BFS(int index);

int BFS(int index) {

    queue<pair<int, int>> q;
    q.push(make_pair(index, 0));

    while(!q.empty()) {

        int node = q.front().first;
        int count = q.front().second;
        q.pop();

        if (isSolution) {
        
            return count;
        }

        for(int i : graph[node]) {
        	
            if(verifyNode(i)){
            	
                visited[node][i] = true;
                q.push(make_pair(i, count + 1));
            }
        }
    }
    return -1;
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int row, col;
    
    cin >> row >> col >> x >> y;
    
    graph.resize(col);
    visited.resize(col, vector<bool> (row, false));
    
    for(int i = 0; i < col; i++) {
    	
        for(int j = 0; j < row; j++) {
        	
            int nextNode;
            cin >> nextNode;
            graph[i].push_back(nextNode);
        }
    }

    cout << BFS(0) << '\n';

    return 0;
}

혹시라도 틀린 내용이 있다면 댓글로 지적해주시면 감사하겠습니다!!