1953번 탈주범 검거

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

해설 : https://www.swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AV7HLJ66CZIDFAXB

처음에 DFS로 풀다가, 실행을 하면서 테스트 케이스과 그림을 확인해보니, DFS로 풀면 안 된다는 것을 깨달았다.

그래서, BFS로 풀었다. 난이도는 쉬웠다.

BFS를 진행하면서 2가지만 확인해주면 됐다.

1. map[행][열]이 0인 곳은 가지 않는다.

2. 상황에 따라 현재 있는 터널 구조물에서 다음 위치(상, 하, 좌, 우)에 있는 터널 구조물로 갈 수 있는지 여부.(go() 함수)

그런데, '제출' 버튼을 클릭하니, 50개의 테스트 케이스 중 49개만 맞다고 떠버렸다.

그래서 무엇이 오류일까 생각하다가

134번 째 줄에 있는 코드(if (thread >= L - 1) return;)를 114번 째로 옮기니, 그제서야 맞다고 떴다.

그래서 뭐가 다른걸까 위치를 잘 생각해봐서, 예외를 생각해보니

1

5 6 2 1 1

0 0 5 3 6 0

0 0 2 0 2 0

3 3 1 3 7 0

0 0 0 0 0 0

0 0 0 0 0 0

위의 예외가 있었다.

134번 째 줄에 있는 코드로 실행했을 때는 3이 나오지만, 

정답이 뜬 114번 째 줄에 있는 코드로 실행했을 때는 1이 나온다.

왜냐하면, 134번 째 줄에 있을 때는 L이 1일 때, 

이미 위에서 while(qSize--)문이 실행된 후(visit가 방문 처리가 됨. )에 실행이 되기 때문이다.

즉, L이 1일 때에는 그 자리에서 바로 끝내야 하는데, 134번 째 줄에 있을 때는 옆으로 이동할 수 있는 터널 구조물이 있기 때문에

방문처리가 되버리기 때문이다.

다음부터는 이런 실수를 줄이도록 해야겠다.

<정답 코드>

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int map[51][51] = { 0, };
 
bool visit[51][51] = { false, };
 
int R = 0, C = 0, L = 0;
int N = 0, M = 0, T = 0;
 
 
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, -1, 0 , 1 };
int dir[4] = { 0, 1, 2, 3 };
//               ↑ ← ↓ →
 
bool go(int before, int after, int d)
{
    if (d == 0) // 위로 이동할 때
    {
        if (before == 3 || before == 5 || before == 6)
        {
            return false;
        }
        else
        {
            if (after == 1 || after == 2 || after == 5 || after == 6)
            {
                return true;
            }
        }
 
        return false;
    }
    else if (d == 1) // 왼쪽으로 이동할 때
    {
        if (before == 2 || before == 4 || before == 5)
        {
            return false;
        }
        else
        {
            if (after == 1 || after == 3 || after == 4 || after == 5)
            {
                return true;
            }
        }
 
        return false;
    }
    else if (d == 2) // 아래로 이동할 때
    {
        if (before == 3 || before == 4 || before == 7)
        {
            return false;
        }
        else
        {
            if (after == 1 || after == 2 || after == 4 || after == 7)
            {
                return true;
            }
        }
 
        return false;
    }
    else if (d == 3) // 오른쪽으로 이동할 때
    {
        if (before == 2 || before == 6 || before == 7)
        {
            return false;
        }
        else
        {
            if (after == 1 || after == 3 || after == 6 || after == 7)
            {
                return true;
            }
        }
 
        return false;
    }
}
 
void BFS(int r, int c)
{
    queue<pair<int, int> > q;
 
    q.push({ r, c });
 
    visit[r][c] = true;
 
    int thread = 0;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int y = q.front().first;
            int x = q.front().second;
 
            q.pop();
 
            if (thread >= L - 1) return;
 
            for (int i = 0; i < 4; i++)
            {
                int ny = y + dy[i];
                int nx = x + dx[i];
                int direction = dir[i];
 
                if (0 <= ny && ny < N && 0 <= nx && nx < M && !visit[ny][nx] && map[ny][nx] != 0 && go(map[y][x], map[ny][nx], direction))
                {
                    visit[ny][nx] = true;
                    
                    q.push({ ny, nx });
                }
            }
        }        
 
        ++thread;
        
        // 내가 틀린 이유
        // if (thread >= L - 1) return;
    }
}
 
int getCount()
{
    int ret = 0;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (visit[i][j])
            {
                ++ret;
            }
        }
    }
 
    return ret;
}
 
int main(void)
{
    scanf("%d", &T);
 
    for (int tc = 1; tc <= T; tc++)
    {
        memset(visit, false, sizeof(visit));
 
        scanf("%d %d %d %d %d", &N, &M, &R, &C, &L);
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                scanf("%d", &map[i][j]);
            }
        }
 
        BFS(R, C);
        
        printf("#%d %d\n", tc, getCount());
    }
 
    return 0;
}