Coding_Test_C++
BaekJoon 17070번: 파이프 옮기기 1(C++)
펄크럼
2021. 7. 16. 01:03
https://www.acmicpc.net/problem/17070
17070번: 파이프 옮기기 1
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의
www.acmicpc.net
해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다.
풀이법
1) BFS를 활용하되 visited배열을 사용하지 않고 문제를 풀었다.
2) 벽지가 긁히면 안되는 것을 꼭 유의하여 특히 대각선으로 움직일때 이동 가능한 모든 경우의 수에서 1이 없는지를 check 후 queue에 넣는 방식을 사용하였다.
이동 가능한 모든 경우의 수는 다음과 같다.
int vx[3] = { 0,1,1 };
int vy[3] = { 1,0,1 };
해당 문제를 품에 있어 사용된 소스 코드는 다음과 같다.
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <math.h>
#include <map>
#define INF 987654321
using namespace std;
int n;
int arr[16][16];
bool visited[16][16];
int vx[3] = { 0,1,1 };
int vy[3] = { 1,0,1 };
int cnt = 0;
void bfs()
{
queue<pair<int, pair<int, int>> >q;
q.push({ 0,{1,0} });
while (!q.empty())
{
int nowX = q.front().first;
int nowY = q.front().second.first;
int nowD = q.front().second.second;
q.pop();
if (nowX == n - 1 && nowY == n - 1)
cnt++;
if (nowD == 0)//가로일 경우
{
int nextX = nowX + vx[0]; //가로 이동
int nextY = nowY + vy[0]; // 가로 이동
if (nextX >= 0 && nextY >= 0 && nextX < n && nextY < n)
{
if (arr[nextX][nextY] != 1)
q.push({ nextX,{nextY,0} });
}
nextX = nowX + vx[2]; //대각선
nextY = nowY + vy[2]; // 대각선
if (nextX >= 0 && nextY >= 0 && nextX < n && nextY < n)
{
bool check = false;
for (int j = 0; j < 3; j++)
{
int checkX = nowX + vx[j];
int checkY = nowY + vy[j];
if (checkX >= 0 && checkY >= 0 && checkX < n && checkY < n)
{
if (arr[checkX][checkY] == 1)
check = true;
}
else
check = true;
}
if (check == false)
q.push({ nextX,{nextY,2} });//대각선
}
}
else if (nowD == 1)
{
int nextX = nowX + vx[1]; //세로 이동
int nextY = nowY + vy[1]; // 세로 이동
if (nextX >= 0 && nextY >= 0 && nextX < n && nextY < n)
{
if (arr[nextX][nextY] != 1)
q.push({ nextX,{nextY,1} });
}
nextX = nowX + vx[2]; //대각선
nextY = nowY + vy[2]; // 대각선
if (nextX >= 0 && nextY >= 0 && nextX < n && nextY < n)
{
bool check = false;
for (int j = 0; j < 3; j++)
{
int checkX = nowX + vx[j];
int checkY = nowY + vy[j];
if (checkX >= 0 && checkY >= 0 && checkX < n && checkY < n)
{
if (arr[checkX][checkY] == 1)
check = true;
}
else
check = true;
}
if (check==false)
q.push({ nextX,{nextY,2} });//대각선
}
}
else if (nowD == 2)
{
int nextX = nowX + vx[0]; //가로 이동
int nextY = nowY + vy[0]; // 가로 이동
if (nextX >= 0 && nextY >= 0 && nextX < n && nextY < n)
{
if (arr[nextX][nextY] != 1)
q.push({ nextX,{nextY,0} });
}
nextX = nowX + vx[1]; //세로 이동
nextY = nowY + vy[1]; // 세로 이동
if (nextX >= 0 && nextY >= 0 && nextX < n && nextY < n)
{
if (arr[nextX][nextY] != 1)
q.push({ nextX,{nextY,1} });
}
nextX = nowX + vx[2]; //대각선
nextY = nowY + vy[2]; // 대각선
if (nextX >= 0 && nextY >= 0 && nextX < n && nextY < n)
{
bool check = false;
for (int j = 0; j < 3; j++)
{
int checkX = nowX + vx[j];
int checkY = nowY + vy[j];
if (checkX >= 0 && checkY >= 0 && checkX < n && checkY < n)
{
if (arr[checkX][checkY] == 1)
check = true;
}
else
check = true;
}
if (check == false)
q.push({ nextX,{nextY,2} });//대각선
}
}
}
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cin >> arr[i][j];
}
bfs();
cout << cnt;
}