반응형
출처
https://swexpertacademy.com/main/solvingProblem/solvingProblem.do
BFS로 구현해서 풀었다. => 제한시간이 촉박하다 느끼는 경우 BFS , 메모리가 부족하다 생각되는 경우 DFS
각 파이프 마다 사방의 위치에서 이어질 수 있는 파이프들에 대한 조건을 각각 지정.
예를 들면 1번 파이프의 왼쪽에는 3,4,5,6번 파이프가 연결되지 않으면 이동 불가.
이동이 가능한 경우 카운트를 올려주고 이동한 지점에 대해서는 visit처리를 해줌. 한 지역에 머무름 방지 ( 시간초과 발생)
그리고 time값을 매개변수로 계속 전달하여 이동한 시간이 탈주범에게 주어진 시간과 같아지는 경우에 break시킴
count는 그전에 올려주기 때문에 상관 없음.
#include<iostream>
#include<queue>
using namespace std;
int arr[50][50];
bool visit[50][50];
int count = 0;
struct Node{
int R;
int C;
int time;
};
int main(void)
{
int test_case;
cin >> test_case;
for(int tc = 1; tc <= test_case; tc++)
{
int N,M,R,C,L;
cin >> N >> M >> R >> C >>L;
queue<Node> que;
count = 0;
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
cin >> arr[i][j];
visit[i][j] = false;
}
}
que.push({R,C,1});
visit[R][C] = true;
count++;
while(!que.empty())
{
int y = que.front().R;
int x = que.front().C;
int time = que.front().time;
que.pop();
if(time == L)
break;
int hole = arr[y][x];
if(hole == 1)
{
if(y>=0 && y<N && x-1>=0 && x-1<M)
{
if(!visit[y][x-1] )
{
if((arr[y][x-1] == 3) || (arr[y][x-1] == 4) || (arr[y][x-1] == 5) || (arr[y][x-1] == 1))
{
visit[y][x-1] = true;
count++;
que.push({y,x-1,time+1});
}
}
}
if(y>=0 && y<N && x+1>=0 && x+1<M)
{
if(!visit[y][x+1] )
{
if((arr[y][x+1] == 3) || (arr[y][x+1] == 6) || (arr[y][x+1] == 7) || (arr[y][x+1] == 1))
{
visit[y][x+1] = true;
count++;
que.push({y,x+1,time+1});
}
}
}
if(y-1>=0 && y-1<N && x>=0 && x<M)
{
if(!visit[y-1][x] )
{
if((arr[y-1][x] == 2) || (arr[y-1][x] == 5) || (arr[y-1][x] == 6) || (arr[y-1][x] == 1))
{
visit[y-1][x] = true;
count++;
que.push({y-1,x,time+1});
}
}
}
if(y+1>=0 && y+1<N && x>=0 && x<M)
{
if(!visit[y+1][x] )
{
if((arr[y+1][x] == 2) || (arr[y+1][x] == 4) || (arr[y+1][x] == 7) || (arr[y+1][x] == 1))
{
visit[y+1][x] = true;
count++;
que.push({y+1,x,time+1});
}
}
}
}
else if(hole == 2)
{
if(y-1>=0 && y-1<N && x>=0 && x<M)
{
if(!visit[y-1][x] )
{
if((arr[y-1][x] == 2) || (arr[y-1][x] == 5) || (arr[y-1][x] == 6) || (arr[y-1][x] == 1))
{
visit[y-1][x] = true;
count++;
que.push({y-1,x,time+1});
}
}
}
if(y+1>=0 && y+1<N && x>=0 && x<M)
{
if(!visit[y+1][x] )
{
if((arr[y+1][x] == 2) || (arr[y+1][x] == 4) || (arr[y+1][x] == 7) || (arr[y+1][x] == 1))
{
visit[y+1][x] = true;
count++;
que.push({y+1,x,time+1});
}
}
}
}
else if(hole == 3)
{
if(y>=0 && y<N && x-1>=0 && x-1<M)
{
if(!visit[y][x-1] )
{
if((arr[y][x-1] == 3) || (arr[y][x-1] == 4) || (arr[y][x-1] == 5) || (arr[y][x-1] == 1))
{
visit[y][x-1] = true;
count++;
que.push({y,x-1,time+1});
}
}
}
if(y>=0 && y<N && x+1>=0 && x+1<M)
{
if(!visit[y][x+1] )
{
if((arr[y][x+1] == 3) || (arr[y][x+1] == 6) || (arr[y][x+1] == 7) || (arr[y][x+1] == 1))
{
visit[y][x+1] = true;
count++;
que.push({y,x+1,time+1});
}
}
}
}
else if(hole == 4)
{
if(y>=0 && y<N && x+1>=0 && x+1<M)
{
if(!visit[y][x+1] )
{
if((arr[y][x+1] == 3) || (arr[y][x+1] == 6) || (arr[y][x+1] == 7) || (arr[y][x+1] == 1))
{
visit[y][x+1] = true;
count++;
que.push({y,x+1,time+1});
}
}
}
if(y-1>=0 && y-1<N && x>=0 && x<M)
{
if(!visit[y-1][x] )
{
if((arr[y-1][x] == 2) || (arr[y-1][x] == 5) || (arr[y-1][x] == 6) || (arr[y-1][x] == 1))
{
visit[y-1][x] = true;
count++;
que.push({y-1,x,time+1});
}
}
}
}
else if(hole == 5)
{
if(y>=0 && y<N && x+1>=0 && x+1<M)
{
if(!visit[y][x+1] )
{
if((arr[y][x+1] == 3) || (arr[y][x+1] == 6) || (arr[y][x+1] == 7) || (arr[y][x+1] == 1))
{
visit[y][x+1] = true;
count++;
que.push({y,x+1,time+1});
}
}
}
if(y+1>=0 && y+1<N && x>=0 && x<M)
{
if(!visit[y+1][x] )
{
if((arr[y+1][x] == 2) || (arr[y+1][x] == 4) || (arr[y+1][x] == 7) || (arr[y+1][x] == 1))
{
visit[y+1][x] = true;
count++;
que.push({y+1,x,time+1});
}
}
}
}
else if(hole == 6)
{
if(y+1>=0 && y+1<N && x>=0 && x<M)
{
if(!visit[y+1][x] )
{
if((arr[y+1][x] == 2) || (arr[y+1][x] == 4) || (arr[y+1][x] == 7) || (arr[y+1][x] == 1))
{
visit[y+1][x] = true;
count++;
que.push({y+1,x,time+1});
}
}
}
if(y>=0 && y<N && x-1>=0 && x-1<M)
{
if(!visit[y][x-1] )
{
if((arr[y][x-1] == 3) || (arr[y][x-1] == 4) || (arr[y][x-1] == 5) || (arr[y][x-1] == 1))
{
visit[y][x-1] = true;
count++;
que.push({y,x-1,time+1});
}
}
}
}
else if(hole == 7)
{
if(y>=0 && y<N && x-1>=0 && x-1<M)
{
if(!visit[y][x-1] )
{
if((arr[y][x-1] == 3) || (arr[y][x-1] == 4) || (arr[y][x-1] == 5) || (arr[y][x-1] == 1))
{
visit[y][x-1] = true;
count++;
que.push({y,x-1,time+1});
}
}
}
if(y-1>=0 && y-1<N && x>=0 && x<M)
{
if(!visit[y-1][x] )
{
if((arr[y-1][x] == 2) || (arr[y-1][x] == 5) || (arr[y-1][x] == 6) || (arr[y-1][x] == 1))
{
visit[y-1][x] = true;
count++;
que.push({y-1,x,time+1});
}
}
}
}
}
cout <<"#"<<tc<<" "<<count<<endl;
}
}반응형
'Algorithm' 카테고리의 다른 글
| 7673. 영이는 영이 시져시져! (0) | 2019.12.29 |
|---|---|
| 1247. [S/W 문제해결 응용] 3일차 - 최적 경로 (0) | 2019.12.28 |
| 4112. 이상한 피라미드 탐험 (0) | 2019.12.22 |
| 1952. [모의 SW 역량테스트] 수영장 (0) | 2019.12.21 |
| 백준 10809 알파벳 찾기 (0) | 2019.12.18 |