백준 26009번 험난한 등굣길

🔒[문제 url]

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

🔑알고리즘

방문할 수 없는 지점을 피해 목적지까지의 최단 경로를 찾는 전형적인 BFS 문제였다.

• 교통 정체 구간을 어떻게 표시할까?
  • 모든 구간에 대해 표시할 필요없이 정체 범위의 테두리에만 표시하여 시간을 단축한다.
  • 반복문을 돌며 정체 범위의 중앙에서 거리가 $D_i$인 모든 지점에 -1을 표기한다.
    
    표기를 마쳤다면, 1 , 1 좌표를 시작으로 BFS 탐색을 진행해 map[n][m]까지 최단 경로를 구한다.

🐾부분 코드

int n, m, k;
int map[3001][3001];
bool visited[3001][3001];
struct block
{
    int r;
    int c;
    int d;
};
vector<block> v;

<변수 선언>
입력할 교통 정체의 정보를 구조체 형태로 선언하여 vector에 입력받는다.

void trafficJam()
{// 교통체증 범위의 테두리에만 표기

    for (int i = 0; i < k; i++)
    {// 체증범위의 갯수만큼 반복

        
		for (int j = 0; j <= v[i].d; j++)
		{// abs(j) + abs(v[i].d - j)는 늘 중심에서 테두리까지의 거리

            int x = j, y = v[i].d - j;

            if (1 <= v[i].r + x && v[i].r + x <= n &&
                1 <= v[i].c + y && v[i].c + y <= m)
            {
                map[v[i].r + x][v[i].c + y] = -1;
            }
            if (1 <= v[i].r - x && v[i].r - x <= n &&
                1 <= v[i].c + y && v[i].c + y <= m)
            {
                map[v[i].r - x][v[i].c + y] = -1;
            }
            if (1 <= v[i].r + x && v[i].r + x <= n &&
                1 <= v[i].c - y && v[i].c - y <= m)
            {
                map[v[i].r + x][v[i].c - y] = -1;
            }
            if (1 <= v[i].r - x && v[i].r - x <= n &&
                1 <= v[i].c - y && v[i].c - y <= m)
            {
                map[v[i].r - x][v[i].c - y] = -1;
            }
		}
    }
}

<교통 정체 구간 표시 함수>
정체범위의 갯수 k만큼 순회하며 맨하튼 거리가 $D_i$ , 즉 v[i].d인 모든 지점에 대해 -1로 표기하여 정체 범위의 테두리를 구별한다.
예를 들어, $D_i = 2$ 이라면 정체 구간은

(+2 , +0) (+2 , -0) (-2 , +0) (-2 , -0)
(+1 , +1) (+1 , -1) (-1 , +1) (-1 , -1)
(+0 , +2) (+0 , -2) (-0 , +2) (-0 , -2)

이다.
또한, map에 대해 out of index가 되지 않도록 주의한다.

void BFS()
{// 최단 경로 BFS 탐색
    queue<pair<int, int>> q;
    q.push({ 1,1 });

    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        visited[x][y] = true;

        int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dir[i][0], ny = y + dir[i][1];
            if (1 <= nx && nx <= n && 1 <= ny && ny <= m)
            {// 범위 체크
                if (!visited[nx][ny] && map[nx][ny] != -1)
                {// 방문하지 않았고, 체증구간이 아니라면
                    q.push({ nx,ny });
                    map[nx][ny] = map[x][y] + 1; // 거리 +1 추가
                    visited[nx][ny] = true;
                }
            }

        }
    }
}

<BFS 함수>
한 칸 이동할 때마다 거리를 1 추가해주며 이동한다.

map[nx][ny] = map[x][y] + 1; // 거리 +1 추가

위 코드를 통해 해당 지점까지의 최단 경로를 표시한다.
탐색이 종료되면, map[n][m]의 값이 출력값이 된다.

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#include <algorithm>
#include <cmath>
// 자료 구조
#include <queue>
#include <vector>
using namespace std;

int n, m, k;
int map[3001][3001];
bool visited[3001][3001];
struct block
{
    int r;
    int c;
    int d;
};
vector<block> v;

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 0; i < k; i++)
    {
        int r, c, d; cin >> r >> c >> d;
        block b = { r,c,d };
        v.push_back(b);
    }
}

void trafficJam()
{// 교통체증 범위의 테두리에만 표기

    for (int i = 0; i < k; i++)
    {// 체증범위의 갯수만큼 반복

        
		for (int j = 0; j <= v[i].d; j++)
		{// abs(j) + abs(v[i].d - j)는 늘 중심에서 테두리까지의 거리

            int x = j, y = v[i].d - j;

            if (1 <= v[i].r + x && v[i].r + x <= n &&
                1 <= v[i].c + y && v[i].c + y <= m)
            {
                map[v[i].r + x][v[i].c + y] = -1;
            }
            if (1 <= v[i].r - x && v[i].r - x <= n &&
                1 <= v[i].c + y && v[i].c + y <= m)
            {
                map[v[i].r - x][v[i].c + y] = -1;
            }
            if (1 <= v[i].r + x && v[i].r + x <= n &&
                1 <= v[i].c - y && v[i].c - y <= m)
            {
                map[v[i].r + x][v[i].c - y] = -1;
            }
            if (1 <= v[i].r - x && v[i].r - x <= n &&
                1 <= v[i].c - y && v[i].c - y <= m)
            {
                map[v[i].r - x][v[i].c - y] = -1;
            }
		}
    }
    

}

void BFS()
{// 최단 경로 BFS 탐색
    queue<pair<int, int>> q;
    q.push({ 1,1 });

    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        visited[x][y] = true;

        int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dir[i][0], ny = y + dir[i][1];
            if (1 <= nx && nx <= n && 1 <= ny && ny <= m)
            {// 범위 체크
                if (!visited[nx][ny] && map[nx][ny] != -1)
                {// 방문하지 않았고, 체증구간이 아니라면
                    q.push({ nx,ny });
                    map[nx][ny] = map[x][y] + 1; // 거리 +1 추가
                    visited[nx][ny] = true;
                }
            }

        }
    }
}

void SOLVE()
{
    trafficJam();

    BFS();

    if (map[n][m]) cout << "YES\n" << map[n][m];
    else cout << "NO";
}


int main()
{
    INPUT();

    SOLVE();
}

🥇문제 후기

골드 하위 문제까지는, 뻔한 알고리즘을 대입만 하면 종종 풀렸다.
골드 상위부터는 알고리즘을 응용해 풀어야하는 문제가 늘어난다고 느껴졌다.
왜냐? 나는 골딱이니까!
이 문제도 처음 읽고나서, "BFS 두번 돌리면 끝이잖아?"를 시전했으나 플래그였다.(시간초과 삐빅)
온라인으로 알게 된 대고수 선생님의 도움을 받아 힘겹게 푼 문제다..ㅋㅋㅋㅋ
알고리즘이 뻔하더라도 최적화하는 방법을 생각하는 연습을 해야겠다.

백준 26009번 문제 세계 최초 포스팅!