[C++] 백준(BOJ) - 14497 : 주난의 난

30 Oct 2023 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

백준(BOJ) - 14497 : 주난의 난(링크)

알고리즘

1. 완전탐색
2. BFS
3. 이중 큐를 이용한 BFS 완전 탐색

풀이

1. 최단거리 탐색 - BFS
2. Leveling (이중 Queue를 활용)
   • 중간 목표에 도달할 때마다 cnt++을 해주어 잠깐 멈췄다가 다시 탐색
   • tmp 는 next point가 된다
   • q에 tmp 값을 다시 집어넣고 다시 탐색

코드

// BOJ-14497 : 주난의 난
#include <bits/stdc++.h>
using namespace std;
#define y1 aaaa

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

int n,m, y1, x1, y2, x2, cnt = 0;
char a[304][304];
int visited[304][304];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> y1 >> x1 >> y2 >> x2;
    y1--, x1--, y2--, x2--;


    for (int i = 0; i < n; i++)
    {
        string str;
        cin >> str;
        for (int j = 0; j < str.size(); j++)
        {
            a[i][j] = str[j];
        }
    }

    queue<pair<int, int>> q;
    q.push({ y1, x1 });
    visited[y1][x1] = 1;

    // 최종 목표지점에 도달하기 전까지 무한 루프
    while (a[y2][x2] != '0')
    {
        cnt++;
        queue<pair<int, int>> tq;

        // 일반적인 BFS 탐색
        while (q.size())
        {
            pair<int, int> tmp = q.front();
            q.pop();

            for (int i = 0; i < 4; i++)
            {
                int ny = tmp.first + dy[i];
                int nx = tmp.second + dx[i];

                if (ny < 0 || nx < 0 || ny >= n || nx >= m || visited[ny][nx]) continue;
                visited[ny][nx] = cnt;
                if (a[ny][nx] != '0') // 0아닌 1값을 만난다면 Leveling, tq에 위치 담아서 다음 탐색을 할때 그 지점부터 시작하게 tempQ 활용
                {
                    a[ny][nx] = '0';
                    tq.push({ ny,nx });
                }
                else q.push({ ny,nx });
            }
        }
        q = tq; // 다음 탐색에 진행할 tq 지점 queue에 담으며 초기화
    }
    
    cout << visited[y2][x2] << '\n';

    return 0;
}

평가

• 일반적인 BFS와 중간 목표 지점에 도달함에 따라 Leveling을 시키는 구조를 짜기위한 알고리즘
• 두 개의 Queue를 활용하여 임시 지점을 저장해 둘 수 있고 queue의 한 size를 모두 돌았을 때 원래 queue에 미리 저장해 둔 tmp queue 값을 초기화하면서 탐색 이어 나가기