[BFS] 1953::탈주범 검거

1953::탈주범 검거

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

1) PASS

2시간 정도 걸린 것 같다. 다음부터는 시간을 재면서 풀어봐야겠다.  예제를 보니 주어진 시간은 이동할 수 있는 노드 레벨의 크기인 것 같아서 bfs로 풀기로 하였다. 가장 시간이 많이 걸린 파트는 아무래도 bfs를 구현하는 부분이었다. 그리고 단순히 값이 0이 아닌 경우는 다 통과할 수 있게 만들어놔서, 파이프 연결 구현을 제대로 못했었다. 

2) BFS

예제)

5 6 2 2 6      
3 0 0 0 0 3
2 0 0 0 0 6
1 3 1 1 3 1
2 0 2 0 0 2
0 0 4 3 1 1

두 번째 케이스를 기준으로 구현했었다. 그런데도 (1,0) 좌표와 (0,0) 좌표를 연결 할 수 없다라는 구현을 안 했다니;; 주어진 좌표를 따라서 방문할 수 있는 그래프를 표현 하면 이렇게 된다.

주어진 값인 (2,2) 부터 level 5까지 갈 수 있는 모든 노드의 갯수를 세서 return하면 된다. 마지막 4.5는 중복되나 visited한 노드를 check하는 array가 있으니깐 신경 안 써도 된다!

3) 노드 레벨 체크 문제

BFS 함수를 구현했을 때,

while(!q.empty())

{

.  .  .

for(int i = 0; i < 4; i++)

{

.  .  .

]

}

이런식으로 구현했다. 여기서 가장 큰 문제는 노드 레벨을 제대로 체크를 못하고 프로그램이 끝나버린다는 것이 었다. 간단한 문제였는데 생각보다 여기서 시간을 많이 썼다. while 문과 for 문 사이에 새로운 queue가 만들어질 때마다 queue의 사이즈를 체크해서 그 사이즈가 0이 될 때까지 while문을 돌리면 해결 된다.

while(!q.empty())

{

int size = q.size();

.    .    .

while(size--)

{

for(int i = 0; i < 4; i++)

{

.  .  .

}

}

}

4) 파이프와 파이프 연결

여기까지 했는데도 값이 제대로 나오지 않았었다. 그래서 제대로 된 노드만을 방문하는 것이 맞는지 다시 한 번 더 체크를 하였는데, 방문해서는 안되는 노드를 방문하고 있었다;; 현재의 x, y값에서는 파이프 방향을 다 체크 했는데 그 다음 방문해야할 x, y값의 파이프 방향은 전혀 고려하지 않고 무작정 방문 체크를 해버리는 바람에 생긴 문제였다. 이 부분은 가야할 방향이 '상'방향인데 그 다음 좌표의 값이 '하'가 아니면 방문할 수 없도록 만들었다. (connect = false)

결국 최종적으로 next값들이 들어갈 수 있는 좌표는

if(is_range(nx, ny) && !vtd[nx][ny] && map[nx][ny] && connect)

{

vtd[nx][ny] = true;

cnt++; 

q.push(pair <int, int>(nx, ny));

}

가 되었다. nx, ny 좌표값이 범위내에 있으면서 && 방문한적이 없어야 하며 && 값이 0이 아니고 && connect가 되어야지만 방문할 수 있도록 만들었다.