푼 사람이 별로 없길래 오랜만에 작성해봅니다 ✌🏻
https://www.acmicpc.net/problem/1400
🔗 문제 해석
조건이 있는 BFS 문제
도로 (N x M, N, M ≤ 20)
- `#` : 갈 수 있는 길
- `.` : 못 가는 길
- `[0-9]` : 조건이 있는 교차로
- 신호주기: A (동서 - ), B (남북 | )
- 시작 방향 - , |
교차로의 신호등은 동서 방향과 남북 방향, 두 개의 신호가 주기적으로 켜진다. 교차로의 신호는 초기에 동서 방향 또는 남북 방향이 될 수 있다. 교차로의 신호 주기를 나타내는 값 "a b"는 동서 방향의 신호가 a 시간 켜지고, 남북 방향의 신호가 b 시간 켜짐을 의미한다.
예를 들어, 초기에 남북 방향의 신호가 켜지고 주기 값이 "2 3"이면, 차량이 1-3 시간에 남북 방향의 신호가 켜지고, 4-5 시간은 동서 방향, 6-8 시간은 다시 남북 방향의 신호가 켜진다.
💭 풀이 과정
지금까지 풀었던 BFS와 비슷한데 교차로에 도착했을 때가 까다로운 문제다.
현재 시간 (time)에 현재 방향 (dir)로 이동하려고 하는데 교차로 신호가 맞는지 확인만 해주면 된다.
구조체 작성
교차로가 정보가 많으니 구조체를 하나 설정하고 K 인덱스에 맞게 저장해줬다.
struct Crossroad
{
int a, b;
bool startVertical;
};
vector<Crossroad> cr(MAX_K);
코드 흐름 구상
교차로가 열렸는지 확인해주는 함수가 필요하겠구나라는 생각과 함께 흐름을 함수로 나눠 아래와 같은 로직을 작성할 수 있다.
bool isValid(x, y) // x, y가 도로를 벗어나는지 확인하는 함수
bool isPass(grid[x][y], dir, crossroad_idx)
int bfs()
{
while(!q.empty())
{
++time;
int qSize = q.size();
while(qSize--)
{
auto [nx, ny] = q.front(); q.pop();
for(int d=0; d<4; ++d)
{
int x, y ; // 이동하려고 하는 좌표
if(!isValid(x, y) || grid[x][y] == '.' || visited[x][y]) continue;
// 여기까지 도달했다면 # 이나 교차로
bool passed = isPass();
// (1). 지나갈 수 있다.
// (2). 지니갈 수 없다면 기다려야 한다.
}
}
}
}
구현에 들어가기 전에 생각을 먼저 해보자.
isPass()의 구현 전에 작성 후 결과를 나눠 생각했다.(위에 코드 참고)
- (1) 지나갈 수 있다면 BFS의 중복연산을 방지하기 위해서 방문처리 (visited)를 하고 큐에 삽입하면 된다.
- (2) 지나갈 수 없다면 큐에서 꺼냈던 “이동 전”의 “제자리”에서 기다린다. -> 제자리를 다시 한번 더 큐에 넣어야 한다.
- 사방탐색을 하는 for문안에서 생성된 좌표는 이동 후 자리이기 때문에 안된다
그러면 아까 작성했던 수도(?)코드의 주석 부분을 아래처럼 구체화 시킬 수 있다.
// 여기까지 도달했다면 # 이나 교차로
bool passed = isPass();
if(passed)
{
visited[x][y] = true;
q.push({x, y});
}
else
{
q.push({nx, ny});
// 제자리라서 방문 처리도 필요 없다.
}
isPass() 구현
현재 좌표로 진행 가능한지 true, false로 반환하는 함수를 작성하려고 한다.
현재 좌표 (x, y)에 time 시간에 dir방향으로 진행 중일 때, 좌표가 교차로k 일 때 교차로 K의 신호 주기가 맞아야만 길이 열린다.
먼저 A, B가 “반복”된다는 것은 주기가 있다는 것이고 주기는 `현재 시간 % 주기`로 정리할 수 있다.
- 주기 (cycle) : A + B
- 현재 상태(rest) : time % cycle
- 근데 여기서는 time이 0부터 시작하므로 `(time-1) % cycle`
그리고 진행하려는 방향 isVertical이랑 교차로 상태랑 같아야만 진행할 수 있으므로 아래처럼 로직을 작성해줬다.
bool isPass(const char road, const int time, const bool isVertical)
{
if(road == '#') return true; // 그냥 갈 수 있는 길
int idx = ch - '0'; // [0~9]의 char형을 int로 변환
auto [a, b, startVertical] = cr[idx];
int cycle = a+b;
int rest = (time-1) % cycle; // 0-based라 1뺌
if(startVertical) // 수평으로 시작하면 AA BBB 반복이니 A보다 작아야한다.
return rest < a ? isVertical : !isVertical; // 지금 교차로가 수평이고 내가 이동하려는 곳도 수평이니 true!
else // 수직부터 시작하면 BBB AA 이런식이니까 b보다 작아야 한다.
return rest < b ? !isVertical : isVertical;
}
isPass()의 또 다른 방법
코드는 더 간단하지만 이해하기 복잡하다...
bool isPass(const char ch, const int time, const bool isVertical)
{
if(ch == '#')
return true;
int idx = ch - '0';
auto [a, b, startVertical] = cr[idx]; //A 동서 - B 남북
int cycle = a + b;
int rest = (time - 1) % cycle;
// 다른 방법
// signalVertical은 교차로가 현재 "수직인지" 담는 변수임
// if 수평 먼저 시작한다면 (A 먼저) then 사이클 연산에 따라 나머지가 A 미만이어야 함
// else if 수직이라면 (B 먼저) then 사이클 연산에 따라 나머지가 A 이상이어야 함
// startVertical (1) : | AAA | BB | AAA | BB ... | time
// startVertical (0) : | BB | AAA | BB | AAA ... | time
bool signalVertical = startVertical ? (rest < a) : (rest >= b);
// 교차로가 열린 시간이랑 현재 교차로 상태랑 비교
return signalVertical == isVertical;
}
🚀 전체 소스
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
constexpr int MAX_N = 20 + 1;
constexpr int MAX_K = 9 + 1;
//북남서동
constexpr int dx[4] = {-1, 1, 0, 0};
constexpr int dy[4] = {0, 0, -1, 1};
int N, M, K;
char grid[MAX_N][MAX_N];
struct Crossroad
{
int a, b;
bool startVertical;
};
vector<Crossroad> cr(MAX_K);
pii start;
bool isValid(const int x, const int y)
{
if(x<0 || y<0 || x>=N || y>=M)
return false;
return true;
}
bool isPass(const char ch, const int time, const bool isVertical)
{
if(ch == '#')
return true;
int idx = ch - '0';
auto [a, b, startVertical] = cr[idx]; //A 동서 - B 남북
int cycle = a + b;
int rest = (time - 1) % cycle;
if (startVertical)
return (rest < a ? isVertical : !isVertical);
else
return (rest < b ? !isVertical : isVertical);
}
int solve()
{
int time = 0;
queue<pair<int, int>> q;
q.push(start);
bool visited[MAX_N][MAX_N] = {false, };
visited[start.first][start.second] = true;
while(!q.empty())
{
int qSize = q.size();
++time;
while(qSize--)
{
auto [nx, ny] = q.front(); q.pop();
bool flag = false;
for(int d=0; d<4; ++d)
{
int x = nx + dx[d];
int y = ny + dy[d];
if(!isValid(x, y) || visited[x][y] || grid[x][y] == '.')
continue;
if(grid[x][y] == 'B')
return time;
bool passed = isPass(grid[x][y], time, !(d < 2));
if(passed)
{
q.push({x, y});
visited[x][y] = true;
continue;
}
flag = true; // nx, ny에서 기다려야 하는 상황 발생
}
// 사방탐색 바깥에 queue를 넣어서 중복 줄이기
if(flag) q.push({nx, ny});
}
}
return -1;
}
int main()
{
while(true)
{
cin >> N >> M;
if(N == 0 && M == 0)
break;
K = -1;
for (int i=0; i<N; ++i)
{
for (int j=0; j<M; ++j)
{
cin >> grid[i][j];
switch (grid[i][j])
{
case 'A': {
start = make_pair(i, j);
break;
}
case '#': case '.': case 'B':
break;
default:
{
int idx = grid[i][j] - '0';
if (K < idx)
K = idx;
break;
}
}
}
}
if(K != -1)
{
int idx, a, b;
char isVertical;
for (int i=0; i<=K; ++i)
{
cin >> idx >> isVertical >> a >> b;
cr[idx] = {a, b, (isVertical == '-')};
}
}
int answer = solve();
if(answer == -1)
cout << "impossible" << "\\n";
else
cout << answer << "\\n";
} // T
return 0;
}