99클럽 코테 스터디 31일차 TIL, 프로그래머스 / 아이템 줍기

https://school.programmers.co.kr/learn/courses/30/lessons/87694

프로그래머스

 

첫번째 풀이 : unordered_map 을 사용하여, 외곽 테두리 정보를 만들어서, 해당 지점을 BFS 로 탐색하는 방법

 

- 하지만 계속 맞지 않았다. 이유는 잘 모르겠다.

#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <iostream>

using namespace std;

static int maxDist = 10000;

unordered_map<int, int> south;
unordered_map<int, int> north;
unordered_map<int, int> west;
unordered_map<int, int> east;

int dRow[] = {0,0,-1,1};
int dCol[] = {-1,1,0,0};

bool totMap[51][51]; // 가능한 경로 : true
int distMap[51][51]; // 해당 지점까지의 최단 거리

// 일단 모든 경로 정보를 후보군에 넣으면 안되는 건가 ?
// 그런데 일단, 외부 테두리를 식별하기는 해야 한다.
// bfs 로 단순히 생각하면, 외부 테두리만 식별하기 어렵다.
// 그러면 외부 테두리를 식별하는 과정을 bfs 로 가능한가 ?
// 그보다, 각 사각형 기준으로 동서남북 외부 테두리 범위는 구할 수 있다.
// 4방향마다, vector 를 만드는 거지.
// 자, 새로운 사각형이 나왔음. 이제 동서남북 마다, update 로직을 수행
// 동 : 같은 y, 작은 x 가 있으면, 그것을 대체
// 서 : 같은 y, 더 큰 x 가 있으면 그것 대체
// 남 : 같은 x, 더 큰 y가 있으면 대체
// 북 : 같은 x, 더 작은 y 가 있으면 대체
void updateNorth(int curX, int curY)
{
    if (north.find(curX) != north.end() && north[curX] >= curY) return;
    north[curX] = curY;    
}

void updateSouth(int curX, int curY)
{
    if (south.find(curX) != south.end() && south[curX] <= curY) return;
    south[curX] = curY;    
}

void updateWest(int curX, int curY)     // 동
{
    if (west.find(curY) != west.end() && west[curY] >= curX) return;
    west[curY] = curX;    
}

void updateEast(int curX, int curY)    // 서
{
    if (east.find(curY) != east.end() && east[curY] <= curX) return;
    east[curY] = curX;    
}

int solution(vector<vector<int>> rectangles, int charX, int charY, int itemX, int itemY) {
    int answer = 0;
    
    for (int r = 0; r < 51; ++r)
    {
        for (int c = 0; c < 51; ++c)
        {
            totMap[r][c]  = false;
            distMap[r][c] = maxDist;
        }
    }
        
    
    for (const vector<int>& rect : rectangles)
    {
        int leftBtmX = rect[0];// 서X
        // cout << "leftBtmX : " << leftBtmX << endl;
        int leftBtmY = rect[1];// 남Y
        // cout << "leftBtmY : " << leftBtmY << endl;
        int rightUpX = rect[2];// 동X
        // cout << "rightUpX : " << rightUpX << endl;
        int rightUpY = rect[3];// 북Y
        
        // 동
        for (int y = rightUpY; y >= leftBtmY; --y)
            updateWest(rightUpX, y);
        // 서
        for (int y = rightUpY; y >= leftBtmY; --y)
            updateEast(leftBtmX, y);
        // 남
        for (int x = leftBtmX; x <= rightUpX; ++x)
            updateSouth(x, leftBtmY);
        // 북
        for (int x = leftBtmX; x <= rightUpX; ++x)
            updateNorth(x, rightUpY);
    }
    
    // x : 열 / y : 행
    cout << "north" << endl;
    for (const auto& pair : north) // f : x = 열 / s : y = 행
    {
        cout << "r,c : " << pair.second << "," << pair.first << endl;
        totMap[pair.second][pair.first] = true;
    }
        
    cout << "south" << endl;
    for (const auto& pair : south) // f : x = 열 / s : y = 행
    {
        cout << "r,c : " << pair.second << "," << pair.first << endl;
        totMap[pair.second][pair.first] = true;
    }
        
    
    cout << "west" << endl;
    for (const auto& pair : west) // f : y = 행 / s : x = 열
    {
        cout << "r,c : " << pair.first << "," << pair.second << endl;
        totMap[pair.first][pair.second] = true;
    }
        
    
    cout << "east" << endl;
    for (const auto& pair : east) // f : y = 행 / s : x = 열
    {
        cout << "r,c : " << pair.first << "," << pair.second << endl;
        totMap[pair.first][pair.second] = true;
    }
        
    
    queue<pair<int/*y : 행*/,int/*x : 열*/>> q;
    q.push({charY, charX});
    distMap[charY][charX] = 0;
    
    while(!q.empty())
    {
        const pair<int,int>& curPos = q.front();
        q.pop();
        
        int curRow = curPos.first;
        int curCol = curPos.second;
        
        for (int i = 0; i < 4; ++i)
        {
            int nxtRow = curRow + dRow[i];
            int nxtCol = curCol + dCol[i];
            int nxtDst = distMap[curRow][curCol] + 1;
            
            // 범위를 벗어날 때
            if (nxtRow < 0 || nxtRow >= 51 || nxtCol < 0 || nxtCol >= 51)
                continue;
            
            // 경로에 없을 때
            if (totMap[nxtRow][nxtCol] == false) continue;
            
            // 지금 경로가 더 비용이 클 때
            if (distMap[nxtRow][nxtCol] <= nxtDst) continue;
            
            distMap[nxtRow][nxtCol] = nxtDst;
            
            q.push({nxtRow, nxtCol});
        }
    }
    
    cout << "totMap" << endl;
    for (int r = 10; r >= 0; --r)
    {
        for (int c = 0; c < 11; ++c)
            cout << totMap[r][c] << ".";
        cout << endl;
    }

    cout << "distMap" << endl;
    for (int r = 10; r >= 0; --r)
    {
        for (int c = 0; c < 11; ++c)
            cout << distMap[r][c] << ".";
        cout << endl;
    }
    
    answer = distMap[itemY][itemX];
    
    return answer;
}