프로그래머스 - 아이템 줍기 - C++

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

프로그래머스

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int answer = 1e9;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };

bool Validation(int x, int y)
{
    if (x >= 0 && x <= 50*2 && y >= 0 && y <= 50*2)
        return true;
    else
        return false;
}

void dfs(vector<vector<int>>& board, int curX, int curY, int cnt)
{
    if (board[curX][curY] == 5)
    {
        if (cnt < answer)
            answer = cnt;

        return;
    }
    board[curX][curY] = 2;
    for (int i = 0; i < 4; i++)
    {
        int nx = curX + dx[i];
        int ny = curY + dy[i];
        // 유효한 좌표이며 굵은 선이면
        if (Validation(nx, ny) && 
            (board[nx][ny] == 1 || board[nx][ny] == 5))
        {
            dfs(board, nx, ny, cnt + 1);
        }
    }
    board[curX][curY] = 1;
}

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {

    vector<vector<int>> board(101, vector<int>(101,0));

    for (auto& item : rectangle)
    {
        // 직사각형의 선을 1로 채우기
        for (int i = item[0]*2; i <= item[2]*2; i++)
        {
            board[i][item[1]*2] = 1;
            board[i][item[3]*2] = 1;
        }
        for (int i = item[1]*2; i <= item[3]*2; i++)
        {
            board[item[0]*2][i] = 1;
            board[item[2]*2][i] = 1;
        }
    }
    for (auto& item : rectangle)
    {
        // 직사각형 안쪽을 2로 채우기
        for (int i = item[0]*2 + 1; i < item[2]*2; i++)
            for (int j = item[1]*2 + 1; j < item[3]*2; j++)
                board[i][j] = 2;
    }
    
    // 아이템 위치 표시
    board[itemX*2][itemY*2] = 5;
    dfs(board, characterX*2, characterY*2, 0);
    return answer/2;
}

사각형의 좌표가 주어지면 그 사각형들의 바깥쪽 테두리를 이용해 현재위치에서 목적지까지의 최단경로를 구하는 문제이다. 

경로를 구할 때 dfs를 이용해왔기에 dfs를 사용하기로 정했다.

 

우선 가장 바깥쪽테두리만 표시하기 위해서 

주어진 사각형 좌표를 기준으로 선을 1로 다 표시하고, 그 후, 각 사각형의 안쪽을 2로 표시했다.

vector<vector<int>> board(101, vector<int>(101,0));

    for (auto& item : rectangle)
    {
        // 직사각형의 선을 1로 채우기
        for (int i = item[0]*2; i <= item[2]*2; i++)
        {
            board[i][item[1]*2] = 1;
            board[i][item[3]*2] = 1;
        }
        for (int i = item[1]*2; i <= item[3]*2; i++)
        {
            board[item[0]*2][i] = 1;
            board[item[2]*2][i] = 1;
        }
    }
    for (auto& item : rectangle)
    {
        // 직사각형 안쪽을 2로 채우기
        for (int i = item[0]*2 + 1; i < item[2]*2; i++)
            for (int j = item[1]*2 + 1; j < item[3]*2; j++)
                board[i][j] = 2;
    }

이 과정에서 자연스레 안쪽의 선들은 2로 덮어씌어진다. 

그런데 보드의 크기가 101x101 인 이유는 가운데가 빈 경로 ㄷ 자의 형태를 표현하기 위함이다. 

 

그 후, 목적지를 5로 표시하고 dfs를 시작한다. 

void dfs(vector<vector<int>>& board, int curX, int curY, int cnt)
{
    if (board[curX][curY] == 5)
    {
        if (cnt < answer)
            answer = cnt;

        return;
    }
    board[curX][curY] = 2;
    for (int i = 0; i < 4; i++)
    {
        int nx = curX + dx[i];
        int ny = curY + dy[i];
        // 유효한 좌표이며 굵은 선이면
        if (Validation(nx, ny) && 
            (board[nx][ny] == 1 || board[nx][ny] == 5))
        {
            dfs(board, nx, ny, cnt + 1);
        }
    }
    board[curX][curY] = 1;
}

목적지에 도착할 때마다 최단경로인지 체크하여 갱신한다. 

for문을 돌기전에 현재 위치를 방문표시하고 for문 종료시 백트래킹을 위해 1로 다시 바꾼다. 

for문에서 4가지 방향에 대해서 갈 수 있다면 dfs로 재귀호출한다. 

 

 

근데 이 문제에서는 dfs가 아니라 bfs가 더 효율적인 방법이라고 chat gpt가 알려줬다. 

최단경로문제에서는 bfs가 더 좋은 효율을 보인다고한다. 

bfs는 처음 찾는 경로가 최단경로인 것을 보장하기 때문이다. 

 

#include <string>
#include <vector>
#include <queue>
using namespace std;

int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };

bool Validation(int x, int y)
{
    if (x >= 0 && x <= 50*2 && y >= 0 && y <= 50*2)
        return true;
    else
        return false;
}

int bfs(vector<vector<int>>& board, int curX, int curY, int endX, int endY)
{
    vector<vector<int>> dist(101,vector<int>(101,-1));
    
    queue<pair<int,int>> q;
    q.push({curX,curY});
    dist[curX][curY]=0;
    while(!q.empty())
    {
        auto [qx,qy] = q.front();q.pop();
        
        if(qx==endX && qy==endY)
            return dist[qx][qy]/2;
        
        for(int i=0;i<4;i++)
        {
            int nx = qx + dx[i];
            int ny = qy + dy[i];
            if(Validation(nx, ny) && board[nx][ny]==1 && dist[nx][ny]==-1)
            {
                q.push({nx,ny});
                dist[nx][ny]=dist[qx][qy]+1;
            }
        }
    }
    return -1;
}

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {

    vector<vector<int>> board(101, vector<int>(101,0));

    for (auto& item : rectangle)
    {
        // 직사각형의 선을 1로 채우기
        for (int i = item[0]*2; i <= item[2]*2; i++)
        {
            board[i][item[1]*2] = 1;
            board[i][item[3]*2] = 1;
        }
        for (int i = item[1]*2; i <= item[3]*2; i++)
        {
            board[item[0]*2][i] = 1;
            board[item[2]*2][i] = 1;
        }
    }
    for (auto& item : rectangle)
    {
        // 직사각형 안쪽을 2로 채우기
        for (int i = item[0]*2 + 1; i < item[2]*2; i++)
            for (int j = item[1]*2 + 1; j < item[3]*2; j++)
                board[i][j] = 2;
    }
    
    return bfs(board, characterX*2, characterY*2, itemX*2,itemY*2);
}

차이는 dfs를 bfs로 바꾼것밖에 없다. 

 

이 문제에서는 실행시간을 봤을 때 dfs가 더 빨랐지만 대체적으로 최단경로에서는 bfs가 빠르다고 하니 앞으로 최단경로에서는 bfs를 써야겠다.