https://www.acmicpc.net/problem/16137
문제
> 견우와 직녀는 여러 섬과 절벽으로 이루어진 지역에서 살고 있다.
> 이 지역은 격자로 나타낼 수 있으며, 상하좌우로 인접한 칸으로 가는 데 1분이 걸린다.
> 7월 7일은 견우와 직녀가 오작교를 건너 만날 수 있는 날이다.
> 그런데 고령화로 인해서 까마귀와 까치가 예전처럼 커다란 오작교를 만들 수 없다.
> 그래서 요즘은 일부 절벽에만 다리를 만들어 주고 있고,
그마저도 힘들어서 몇 분 주기로 오작교를 짓고 해체하는 작업을 반복해야 한다.
> 한 번 지은 오작교는 1분 동안 유지할 수 있다.
> 예를 들어 오작교가 3분과 4분 주기라면,
건널 수 있는 시간은 아래 그림에서 초록색으로 표시한 부분과 같다.
> 오작교는 이처럼 매우 불안정하므로,
견우는 안전을 위해 두 번 연속으로 오작교를 건너지는 않기로 했다.
> 까마귀와 까치는 조금이라도 견우를 더 도와주기 위해,
절벽을 정확히 하나 골라 주기가 M분인 오작교를 하나 더 놓아 주기로 했다.
> 단, 이미 오작교를 짓기로 예정한 절벽에는 오작교를 하나 더 놓을 수 없고,
아래와 같이 절벽이 가로와 세로로 교차하는 곳에도 오작교를 놓을 수 없다.
> 아래 그림에서 파란색은 견우가 건널 수 있는 일반적인 땅,
검은색은 절벽, 흰색은 절벽이 교차해서 오작교를 놓을 수 없는 위치를 나타낸다.
> 견우가 직녀에게 도착할 수 있는 최소의 시간을 찾아 보자.
접근
땅이 최대 10x10짜리 크기이고 100개가 존재하는데 이 중 교차된 절벽을 전부 쳐내면 실제 오작교를 설치 할 수 있는 절벽이 많지않다. 그래서 땅을 입력받으면서 0인 좌표에 대해 각각 상,하,좌,우가 범위를 넘어가지않으면서 주변에 절벽이 있는지 확인하고 가로, 세로에 둘다 절벽이 있으면 교차이므로 아닌 절벽들만 따로 모아둔다.
입력받은 땅에 앞서 모아둔 절벽의 좌표에 입력받은 주기의 오작교를 미리 만들어 놓고 각각의 경우에 BFS를 행한다.
각각의 경우에서 나온 최소 시간을 min연산으로 전부 비교해 가장 최소의 시간을 고른다.
문제해결
> 땅의 크기, 오작교의 주기를 입력받고 area벡터에 땅의 상태를 입력받는다.
> 땅이 0이 아니면 넘어가고 해당 절벽의 위에 범위를 넘어가지 않는 절벽이 있거나
아래에도 범위를 넘어가지 않는 절벽이있는지 와 동시에
좌측이나 우측에도 범위를 넘어가지않는 절벽이있는지 본다.
> 있다면 절벽이 교차된 지점이라는 뜻이므로 넘어간다.
> 위 두 조건을 모두 만족한 절벽은 오작교를 만들 수 있는 절벽이므로 wall벡터에 좌표를 모아둔다.
> 이제 모아둔 좌표를 하나씩 꺼내 땅에 M주기로 오작교를 설치해주고 각각의 경우에 BFS를 한다.
> 방문처리도 매번 새로 갱신해주고, BFS가끝나면 땅을 다시 오작교 설치 전으로 되돌린다.
> BFS에선 큐에 행,열 좌표와 지금까지 걸린 시간을 받는다.
> 탐색이 끝나는 조건은 N-1,N-1인 직녀가 있는 좌표에 도달했을 때 이고, 이때 각 BFS를 돌며 나온 최소값을 비교해 갱신한다.
> 사방 탐색으로 경로를 탐색하는데 새 경로가 범위를 넘어가거나, 이미 갔던 곳이면 탐색하지않는다.
> 두 가지 경우가 있는데 땅이 1인 갈 수 있는 땅이면 큐에 경로로 넣고, 방문처리를 해준다.
> 다음은 2이상인 오작교일 때이다.
다음 좌표가 오작교일 때, 현재의 좌표를 확인하는데 만약 현재의 좌표도 오작교라면 연속이 불가능하므로 탐색하지않는다.
> 그게 아니라면 현재까지 걸린 시간+1초가 이제 갈 오작교의 주기와 맞는지 확인한다.
> 맞다면 오작교로 이동하고 방문처리해주지만 주기가 다르다면 해당 주기가 올 때 까지 가만히 기다리는 경우도 큐에 1초씩 증가하며 넣어준다.
> 최종적으로 걸리는 최소시간이 저장된 rst를 출력한다.코드
#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <climits>
#include <algorithm>
#include <queue>
using namespace std;
int N, M;
int rst = INT_MAX;
int dir[4] = { -1, 1, 0, 0 };
int dic[4] = { 0, 0, -1, 1 };
vector<vector<int>> area;
vector<vector<bool>> visited;
vector<pair<int, int>> wall;
struct state {
int row, col, time;
};
void BFS(int sr, int sc, int st)
{
queue<state> q;
q.push({ sr, sc, st });
visited[sr][sc] = true;
while (!q.empty())
{
int fr = q.front().row;
int fc = q.front().col;
int ft = q.front().time;
q.pop();
if (fr == N - 1 && fc == N - 1)
{
rst = min(rst, ft);
return;
}
for (int i = 0; i < 4; i++)
{
int nr = fr + dir[i];
int nc = fc + dic[i];
int nt = ft + 1;
if (nr < 0 || nr >= N) continue;
if (nc < 0 || nc >= N) continue;
if (visited[nr][nc]) continue;
if (area[nr][nc] == 1) //갈 수 있는 땅이면
{
if (!visited[nr][nc])
{
q.push({ nr, nc, nt});
visited[nr][nc] = true;
}
}
else if (area[nr][nc] >= 2) //갈 곳이 오작교면
{
if (area[fr][fc] >= 2) continue; //오작교 연속 불가
if (nt % area[nr][nc] != 0) q.push({fr, fc, nt});
else
{
q.push({nr, nc, nt});
visited[nr][nc] = true;
}
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
area.resize(N, vector<int>(N));
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> area[i][j];
for (int i = 0; i < N; i++) { //교차 절벽 처리
for (int j = 0; j < N; j++) {
if (area[i][j] != 0) continue;
if (((i - 1 >= 0 && area[i - 1][j] == 0) || (i + 1 < N && area[i + 1][j] == 0)) &&
((j - 1 >= 0 && area[i][j - 1] == 0) || (j + 1 < N && area[i][j + 1] == 0))) {
continue;
}
wall.push_back({ i,j });
}
}
for (auto w : wall)
{
visited.assign(N, vector<bool>(N, false));
area[w.first][w.second] = M;
BFS(0, 0, 0);
area[w.first][w.second] = 0;
}
cout << rst << '\n';
}
후기
처음에 벽 뚫고 지나가기 문제같은 흐름으로 생각해 방문처리를 3차원으로 주고 0,1로 뚫었냐 안뚫었냐를 따져 각각의 최소시간을 구하려고했다. 하지만 이때, 오작교 앞에서 가만히 기다리는 경우에 대해 큐에 계속 들어가며 시간초과가 났다.
그래서 N이 작은걸 이용해 브루트포스 느낌으로 가능한 오작교를 손수 따져 했다.
