https://www.acmicpc.net/problem/17070
문제
> 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다.
> 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.
> 파이프를 밀어서 이동시키고, 벽을 긁으면 안되며, 항상 빈칸만 차지해야한다.
> 파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다.
파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.
> 파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다.
> 가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자
접근
그래프탐색(BFS)를 이용해 현재 위치에서 나아갈 수 있는 위치의 경우를 모두 구하고 각 경우에서 또 나아갈수 있는 경로를 탐색하며 목적지에 도달하면 cnt값을 누적해 최종적으로 출력한다.
문제해결
> 먼저 집의 크기(N), 집의 벽 위치(house), 가능한 방법의 수(cnt), 가능한 진행방향(dr,dc) 각각 가로 세로 대각선 순서로 정의해준다.
> BFS를 통해 경로를 탐색하는데 큐에 row, col에 추가로 가로,세로,대각선에 대한 상태도 주어야하므로 큐에 원소를 세개 줘야해서 struct로 정의해준다.
> 큐를 선언하고 처음 파이프의 위치를 넣어준다. 현재 front에 있는 r,c,d값을 각각 가져온 뒤 제거해준다.
탐색 조건을 만족했을 때의 처리(방법수 cnt누적, 탐색끝났으므로 다음 경우 탐색)를 해준다.
> 가로 세로 대각선에 대해 가능한 진로를 다음 탐색으로 넣기위해 3방향에대해 반복해주면서 일단 갈 수 없는 경로에 대한 처리를 해준다.
> 가로(0)은 세로(1)로 못가고 세로(1)는 가로(0)로 못가므로 fd와 i의 합이 1일 때 continue해서 넘어간다.
> 그 이외엔 현 위치 fr,fc에 dr,dc를 연산해 다음 경로를 계산해주고 방향도 설정한다.
> 오류나는 경우, 0보다 작거나, N을 넘어가는경우에 대해 처리해주고 여기서 추가로 대각선으로 갈 땐 꼭 빈칸이어야 하는 곳이 추가로 두 곳 더있으므로 그에대한 처리를 해준다. 만약 그 곳이 1이면 탐색하지 않는다.
> 위의 조건을 만족하는 경로를 큐에 추가해면서 위 과정을 반복한다. 최종적으로 탐색이 끝나 큐가 비어 while문이 깨지면 누적된 cnt를 반환한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int N;
int dr[3] = { 0, 1, 1 }; //가 세 대
int dc[3] = { 1, 0, 1 };
int house[17][17];
int cnt = 0;
struct Node
{
int row, col, dir;
};
int pipe(int r, int c, int d)
{
queue<Node> q;
q.push({ r, c, d });
while (!q.empty())
{
int fr = q.front().row;
int fc = q.front().col;
int fd = q.front().dir;
q.pop();
if (fr == N && fc == N)
{
cnt++;
continue;
}
for (int i = 0; i < 3; i++)
{
if (fd + i == 1) continue;
int nr = fr + dr[i];
int nc = fc + dc[i];
int nd = i;
if (house[nr][nc] == 0 && nr >= 0 && nr <= N && nc >= 0 && nc <= N)
{
if (i == 2)
{
if (house[nr - 1][nc] == 1 || house[nr][nc - 1] == 1) continue;
}
q.push({ nr, nc, nd });
}
}
}
return cnt;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++) cin >> house[i][j];
}
cout << pipe(1, 2, 0) << '\n';
}
후기
파이프의 이동에 대해 문제가 모호해서 이해하기 힘들었지만 문제를 이해하고나니 사방탐색과 비슷한 양상의 문제다. 거기에 추가로 갈 수 없는 방향의 예외 처리, 꼭 비어있어야하는 곳 등등 조건이 붙는다.
큐의 원소로 3개 이상을 넣는건 처음이라 이 부분을 새로 배웠다. 막상 풀고나니 깔끔하고 괜찮았다.
