Life Engineering
[BOJ 17070] 파이프 옮기기 (C++) 본문
https://www.acmicpc.net/problem/17070
#include <bits/stdc++.h>
using namespace std;
enum Pos {garo, sero, degak};
int house[17][17];
class Point{
public:
int y;
int x;
Pos pos;
Point(int y, int x, Pos pos){
this->y=y;
this->x=x;
this->pos=pos;
}
};
bool isPossible(int y, int x){
if (house[y+1][x]==0 && house[y][x+1]==0 && house[y+1][x+1]==0){
return true;
}
else{
return false;
}
}
int main(){
int N, x;
cin>>N;
int visited[3][N+1][N+1];
memset(visited, 0, sizeof(int)*3*(N+1)*(N+1));
int cnt=0;
for (int i=1; i<=N; i++){
for (int j=1; j<=N; j++){
cin>>x;
house[i][j]=x;
}
}
queue<Point *> q;
q.push(new Point(1,2,garo));
//visited[garo][1][2]=1;
while (!q.empty()){
Point *p=q.front();
q.pop();
if (p->y==N && p->x==N){
cnt++;
//visited[p->pos][p->y][p->x]=0;
continue;
}
int nx=(p->x)+1;
int ny=(p->y)+1;
if (p->pos==garo){
if (nx>=1 && nx<=N){
if (house[p->y][nx]==0){
//visited[garo][p->y][nx]=1;
q.push(new Point(p->y, nx, garo));
}
}
if (ny>=1 && ny<=N && nx>=1 && nx<=N){
if (isPossible(p->y, p->x)){
//visited[degak][ny][nx]=1;
q.push(new Point(ny, nx, degak));
}
}
}
else if (p->pos==sero){
if (ny>=1 && ny<=N){
if (house[ny][p->x]==0){
//visited[sero][ny][p->x]=1;
q.push(new Point(ny,p->x,sero));
}
}
if (ny>=1 && ny<=N && nx>=1 && nx<=N){
if (isPossible(p->y, p->x)){
//visited[degak][ny][nx]=1;
q.push(new Point(ny, nx, degak));
}
}
}
else{
if (nx>=1 && nx<=N){
if (house[p->y][nx]==0){
//visited[garo][p->y][nx]=1;
q.push(new Point(p->y, nx, garo));
}
}
if (ny>=1 && ny<=N){
if (house[ny][p->x]==0){
//visited[sero][ny][p->x]=1;
q.push(new Point(ny,p->x,sero));
}
}
if (ny>=1 && ny<=N && nx>=1 && nx<=N){
if (isPossible(p->y, p->x)){
//visited[degak][ny][nx]=1;
q.push(new Point(ny, nx, degak));
}
}
}
}
cout<<cnt<<"\n";
return 0;
}
BFS 로 탐색하는 문제.
그러나 다른점은 visited 배열을 사용할 필요 없다는거! (너무 정형화된 생각을 하는 바람에 visited 배열을 만들어서 괜히 헤맴)
어차피 이동 방향이 무한 루프를 돌 수 없는 구조로 설정되어있다.
그리고 최단 거리를 구하는게 아니라 (N, N) 까지 도달하는 가짓수를 구하는 것임에 유의하기.
코드를 간결하게 짜지 못한거 같다.
다른 분의 코드를 보니 (출처: https://binux.tistory.com/36 ) 탐색할 수 있는 위치인지 파악하는 함수를 따로 만들고(벽인지 체크, 경계를 벗어나는지 체크, direction에 따라 벽을 체크한다), 이동하는 함수를 따로 만들면 간결해짐을 알 수 있었다.
이동 방향을 주고 현 가로방향이면 move(세로방향), move(대각선방향) 이런 식으로.
가능한지 체크하고->가능하면 큐에 이동방향에 맞게 넣어주고->(n,n) 일때 카운팅해주면 된다.
'Problem Solving' 카테고리의 다른 글
[BOJ 7578] 공장 (C++) (0) | 2021.08.20 |
---|---|
[BOJ 1238] 파티 (C++) (0) | 2021.08.19 |
[BOJ 3830] 교수님은 기다리지 않는다 (C++) (0) | 2021.08.18 |
[BOJ 2357] 최솟값과 최댓값 (C++) (0) | 2021.08.17 |
[BOJ 9466] 텀 프로젝트 (C++) (0) | 2021.08.17 |