아이템 줍기 87694

문제

접근 방법

3가지를 생각했다.
1. 그래프로 생각하여 BFS (꼭짓점 간의 거리)
2. 경계 지점을 체크하여 BFS
3. 변의 길이는 같다는 것 (울퉁불퉁하면 안된다)

	O	O	O
O	O	O	O	O
O	O	O	O	O

만약 울퉁불퉁하지 않다면 둘레는 같다는 것이다.

	O		O
O	O	O	O	O
O	O	O	O	O

물론 울퉁불퉁한 것이 분명히 나올 것이기에 3번은 불가능하다.
1번은 규칙을 찾아야 하는데 (울퉁불퉁할 때 꼭짓점이 존재하는지, 내부에 들어간 꼭짓점이 아닌지) 힘들 것 같기에 2번으로 접근하였다.
처음에는 다음 위치의 8방향을 확인하여 도형 안에 있는지 확인하는 방식으로 하려 했다. 생각하다 보니 겉 부분만 도는 거면 겉 부분만 색칠하면 될 것 같았다.

진행하다가 도저히 접근을 못 하겠어서 약간 찾아봤다. 대략 2배로 보고 다시 2로 나누는 방식으로 해결하는 것임을 알게 됐다. 간단하지만 생각만으로 범접할 수 있는 영역은 아니라고 생각하여 찾아본 게 나은 것 같다.

#include <string>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
int dx[] = {1, -1, 0, 0, 1, 1, -1, -1}, dy[] = {0, 0, 1, -1, 1, -1, 1, -1};
int map[201][201];
int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY)
{
    queue<pair<int, int>> bfs;
    for (auto pos : rectangle)
        for (int i = (pos[1] << 1); i <= (pos[3] << 1); ++i)
            for (int j = (pos[0] << 1); j <= (pos[2] << 1); ++j)
            {
                map[i][j] = INT_MAX;
            }
    for (auto pos : rectangle)
        for (int i = (pos[1] << 1) + 1; i < (pos[3] << 1); ++i)
            for (int j = (pos[0] << 1) + 1; j < (pos[2] << 1); ++j)
            {
                map[i][j] = 0;
            }
    itemX <<= 1;
    itemY <<= 1;
    characterX <<= 1;
    characterY <<= 1;
    map[characterY][characterX] = 1;
    bfs.push({characterY, characterX});
    while (!bfs.empty())
    {
        auto cur = bfs.front();
        if (cur.first == itemY && cur.second == itemX)
            break;
        bfs.pop();
        for (int i = 0; i < 4; ++i)
        {
            pair<int, int> next = {cur.first + dy[i], cur.second + dx[i]};
            if (!map[next.first][next.second] || map[next.first][next.second] != INT_MAX) // 사각형 안에 있는가?, 이미 탐색한 곳인가?
                continue;
            map[next.first][next.second] = map[cur.first][cur.second] + 1;
            bfs.push({next.first, next.second});
        }
    }
    return (map[bfs.front().first][bfs.front().second] >> 1);
}

풀이

처음에 선만 그어서 이용하려 했는데 도형이 겹쳐서 들어가는 선이 있으니 안될 것 같았다. (그리하면 지름길이 생긴다)
그래서 8방향을 확인하는 방식으로 했는데 잘 안됐었다. 다른 사람들 거를 잠깐 봤었다. 칠하고 다시 범위를 좁혀서 칠하면 겉 부분만 나온다는 간단한 방법을 떠올리지 못했다는 거에 아쉬움이 좀 남았고 2배하고 다시 2로 나눈다는 점은 시간을 계속 사용했어도 다른 거에 꽂혔던 상태였기에 도달 못 하지 않았을까 싶어서 참고하길 잘한 것 같다.
현재 기준 코딩테스트 고득점 Kit에 있는 탐색 문제 중 가장 어려웠던 것 같다.