티스토리 뷰
1. 문제 링크
2931번: 가스관
러시아 가스를 크로아티아로 운반하기 위해 자그레브와 모스코바는 파이프라인을 디자인하고 있다. 두 사람은 실제 디자인을 하기 전에 파이프 매니아 게임을 이용해서 설계를 해보려고 한다.
www.acmicpc.net
2. 문제 개요
가스를 M에서 Z로 옮기려고 파이프라인을 디자인하고 있다.
파이프의 종류는 다음과 같다.
파이프 라인의 설계를 마친 두 사람은 저녁을 먹으러 갔는데 그 사이 해커가 침입해 블록 하나를 지웠다. 지운 블록은 빈칸이 되어있다. 해커가 어떤 칸을 지웠고, 그 칸에는 원래 어떤 블록이 있었는지 구하는 프로그램을 작성하시오.
3. 문제 힌트
맵의 총 크기는 25*25로 그렇게 크지는 않다.
어떤 파이프를 찾으려고 할 때 모든 빈칸에 넣어서 확인하는 방식으로 진행해도 괜찮을 것 같다.
그렇다면 가스를 흘려보는 것은 어떻게 구현해야 할까? →BFS
가스가 움직이는 방향은 파이프에 따라 다르니까 흐르는 것을 담당하는 함수를 구현해야 한다.
예를 들어 - 모양 파이프 같은 경우, 위쪽에서 가스가 들어온다면 흐를 수 없다 라고 판단해야 함.
여러 가지 예외 케이스가 있음. -나 |로 해결할 수 있는데 + 가 와서는 안된다거나, 모든 파이프는 1번 이상 가스가 흘러야 한다(모든 파이프는 쓸모가 있음) 라거나..
M와 Z가 인접한 경우도 고려해야 함(이것 때문에 맞왜틀...).
모든 경우의 수로 파이프를 넣어보기 때문에 가스가 무한정 순환하는 경우가 있다. 이것도 체크해줘야 함.
4. 문제 풀이
우선 맵 입력을 받기 전에 필요한 자료구조 먼저 보자,
좌표를 나타내는 COORD 구조체를 선언했다.
행, 열 정보를 갖고 있고, 또 중요한 것은 어느 방향으로부터 왔는지가 중요하다. 그렇게 해야 3번에서 말했던 문제를 해결할 수 있다. ( -모양 파이프인데 위에서 오는 경우)
그리고 맵을 입력받고,
0행 0열부터 빈칸에 블록 7가지를 모두 놓아볼 것이다. 이때, -나 |로 해결할 수 있는데 +가 와서는 안되기 때문에 +는 놓는 순서중 가장 마지막에 위치시키도록 하자.
이제 맵의 모든 곳을 방문하면서 빈칸인 경우 블록을 놓을 것이다.
그럼 놓고 이제 BFS를 통해서 시작점부터 종료점까지 제대로 흐르는지 확인할 것이다.
Queue에 시작점을 넣고 방문 처리하자. 방문처리하는 이유는 모든 파이프가 사용되어야 한다는 조건이 있기 때문이다.
도착점에 도착했을 때, 방문하지 않은 파이프가 있다면 도착했더라도 답이 될 수 없다. 그래서 필요하다.
그리고 파이프를 모두 다 대입해보기 때문에 정답이 아닌 경우 가스가 무한정 순환할 수 있다. 그래서 방문 횟수가 많아지면 BFS탐색을 멈추는 그런 부분이 필요하다.
그러면 시작점으로부터 인접한 4칸을 확인해서 연결된 부분부터 시작하도록 하자,
이제 가스가 흐르는 함수를 정의할 필요가 있다.
생각대로 하면 된다. | 모양을 예로 들면, 위에서 들어온 경우 위에서 들어왔다고 하고, 밑으로 한 칸 내려주면 된다. 밑에서 들어온 경우는 밑에서 들어왔다고 하고 위로 올려주면 된다.
ㄱ모양을 예로 들면, 왼쪽에서 들어온 경우 위쪽에서 들어왔다고 하고 밑으로 내려주면 된다. 밑에서 들어온 경우 오른쪽에서 왔다고 하고 왼쪽으로 보내 주면 된다. 이렇게 모두 적용시켜주자,
하지만 이렇게 이동하는데 경계선 밖으로 나가게 되면 움직일 수 없으므로 ERROR를 의미하는 특정한 값을 반환시켜주도록 하자.
Move() 함수로 정의했다.
그리고 최대 반복 횟수를 r*c*2로 한 이유는 +파이프는 2번 방문하게 된다. 그래서 방문 횟수가 모든 칸*2가 된다면 불필요하게 방문을 계속하고 있는 것으로 판단하고 BFS탐색을 그만두도록 했다.
5. 코드
#include <cstdio>
#include <queue>
using namespace std;
const int East = 0, West = 1, South = 2, North = 3;
struct COORD {
COORD() {}
COORD(int y_, int x_, int from_) :y(y_), x(x_), from(from_) {}
int y, x;
int from; //0:East, 1:West, 2:South, 3:North
};
char map[25][25];
int r, c;
COORD start, finish;
const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };
char const block[] = { 124,'-','1','2','3','4','+' };
COORD Move(COORD cur)
{
COORD next(-1,-1,-1);
if (map[cur.y][cur.x] == '|')
{
if (cur.from == South)
{
next.y = cur.y - 1;
next.x = cur.x;
next.from = South;
}
else if (cur.from == North)
{
next.y = cur.y + 1;
next.x = cur.x;
next.from = North;
}
else
next = COORD(-1, -1, -1);
}
else if (map[cur.y][cur.x] == '-')
{
if (cur.from == East)
{
next.y = cur.y;
next.x = cur.x - 1;
next.from = East;
}
else if (cur.from == West)
{
next.y = cur.y;
next.x = cur.x + 1;
next.from = West;
}
else
next = COORD(-1, -1, -1);
}
else if (map[cur.y][cur.x] == '+')
{
if (cur.from == East)
{
next.y = cur.y;
next.x = cur.x - 1;
next.from = East;
}
else if (cur.from == West)
{
next.y = cur.y;
next.x = cur.x + 1;
next.from = West;
}
else if (cur.from == South)
{
next.y = cur.y - 1;
next.x = cur.x;
next.from = South;
}
else if (cur.from == North)
{
next.y = cur.y + 1;
next.x = cur.x;
next.from = North;
}
}
else if (map[cur.y][cur.x] == '1')
{
if (cur.from == South) //to East
{
next.y = cur.y;
next.x = cur.x + 1;
next.from = West;
}
else if (cur.from == East) //to South
{
next.y = cur.y + 1;
next.x = cur.x;
next.from = North;
}
}
else if (map[cur.y][cur.x] == '2')
{
if (cur.from == North) //to East
{
next.y = cur.y;
next.x = cur.x + 1;
next.from = West;
}
else if (cur.from == East) //to North
{
next.y = cur.y - 1;
next.x = cur.x;
next.from = South;
}
}
else if (map[cur.y][cur.x] == '3')
{
if (cur.from == North) //to West
{
next.y = cur.y;
next.x = cur.x - 1;
next.from = East;
}
else if (cur.from == West) //to North
{
next.y = cur.y - 1;
next.x = cur.x;
next.from = South;
}
}
else if (map[cur.y][cur.x] == '4')
{
if (cur.from == South) //to West
{
next.y = cur.y;
next.x = cur.x - 1;
next.from = East;
}
else if (cur.from == West) //to South
{
next.y = cur.y + 1;
next.x = cur.x;
next.from = North;
}
}
else if (map[cur.y][cur.x] == '.')
{
next.y = -1;
next.x = -1;
next.from = -1;
}
//boundary check
if (next.x < 0 || next.y < 0 || next.x >= c || next.y >= r)
return COORD(-1, -1, -1); //error
return next;
}
int main()
{
scanf("%d %d", &r, &c);
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j) {
scanf("%c", &map[i][j]);
if (map[i][j] == '\n')
j--;
else if (map[i][j] == 'M') {
start.x = j;
start.y = i;
start.from = -1;
}
else if (map[i][j] == 'Z') {
finish.x = j;
finish.y = i;
finish.from = -1;
}
}
//Brute force
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) {
if (map[i][j] == '.') {
for (int k = 0; k < 7; ++k) {
//random pipe
map[i][j] = block[k];
//bfs
queue<COORD> q;
bool visited[25][25] = { false };
visited[start.y][start.x] = true;
int count = 0;
//init
for (int dir = 0; dir < 4; ++dir)
{
COORD next;
next.y = start.y + dy[dir];
next.x = start.x + dx[dir];
if (next.x < 0 || next.y < 0 || next.x >= c || next.y >= r || map[next.y][next.x] == '.' || map[next.y][next.x] == 'Z')
continue;
if (dir == East) {
next.from = West;
if (map[next.y][next.x] == '|' || map[next.y][next.x] == '1' || map[next.y][next.x] == '2')
continue;
}
else if (dir == West) {
next.from = East;
if (map[next.y][next.x] == '|' || map[next.y][next.x] == '3' || map[next.y][next.x] == '4')
continue;
}
else if (dir == South) {
next.from = North;
if (map[next.y][next.x] == '-' || map[next.y][next.x] == '1' || map[next.y][next.x] == '4')
continue;
}
else if (dir == North) {
next.from = South;
if (map[next.y][next.x] == '-' || map[next.y][next.x] == '2' || map[next.y][next.x] == '3')
continue;
}
q.push(next);
}
//flow
while (!q.empty())
{
COORD cur = q.front(); q.pop();
visited[cur.y][cur.x] = true;
++count;
if (count == r * c * 2)
break;
if (map[cur.y][cur.x] == 'Z')
{
bool findans = true;
//모두 돌았는지 검사
for (int a = 0; a < r; ++a)
for (int b = 0; b < c; ++b)
if (map[a][b] != '.' && visited[a][b] == false)
findans = false;
if (!findans)
break;
printf("%d %d %c", i + 1, j + 1, block[k]);
return 0;
}
COORD next = Move(cur);
if (next.y == -1 && next.x == -1 && next.from == -1)
continue;
q.push(next);
}
}
map[i][j] = '.';
}
}
}
return 0;
}
6. 결과
'알고리즘 > Implementation' 카테고리의 다른 글
| boj, 백준) 17435. 합성함수와 쿼리 (C / C++) (0) | 2021.04.24 |
|---|---|
| boj, 백준) 7682. 틱택토 ( C / C++ ) (1) | 2020.12.20 |
| boj, 백준) 1655. 가운데를 말해요 ( C / C++) (0) | 2020.06.22 |
| boj) 1021 회전하는 큐 (C++) (0) | 2020.02.17 |
| boj) 5397 키로거 ( C / C++) (0) | 2020.02.15 |