[L3] 프로그래머스 아이템 줍기 C++ BFS, 좌표 확장

리뷰

프로그래머스

 

2차원 좌표 평면에서 주어진 사각형의 테두리만 타서 목표에 도달하여 아이템을 줍는 문제

선분을 타고 이동하는 문제는 대체로 좌표를 확장하여 문제를 푸는 것 같다.

 

 

전역 변수

• v : 이동한 좌표를 방문처리를 해주기 위한 정수형 배열, 최대 크기의 2배인 101 * 101로 초기화 한다.
• lst : 맵 정보를 초기화 하기 위한 정수형 배열, 크기는 상동
• dx, dy : 상하좌우 이동을 위한 방향 배열
• Pos : 너비 우선 탐색 시 현재 위치 정보와 소요 시간을 저장하는 구조체

 

함수

1. bfs

int bfs(int sx, int sy, int ex, int ey)

 

너비 우선 탐색을 통해 목표 위치로 이동하는 최소값을 구하는 함수

1. 매개변수로 시작 위치의 x, y좌표와 도착 위치의 x, y좌표를 입력 받는다.
2. Pos타입의 큐 q를 초기화 하고 q에 시작 위치 x, y좌표 및 소요시간 0을 push해준다.
3. 시작 위치 x, y좌표를 방문 처리 해주고, 큐가 빌때까지 BFS를 실행한다.
4. 큐에서 위치를 꺼내고 만약 도착위치에 도달했다면 소요 시간을 2로 나눈 값을 리턴해 준다.
5. 도착위치가 아니라면 4방향을 탐색하고, 범위 내 이면서 방문하지 않았고, 맵 상에서 0이라면 이동해준다.
6. 이동한 좌표를 방문처리 해주고 큐에 이동한 좌표와 소요시간을 증가한 값을 추가해 준다.

 

문제풀이

1. 맵의 모든 바탕을 임의의 값으로 초기화 해준다. 나는 memset메서드를 통해 -1로 초기화 해주었다.
2. 사각형 벡터를 순회하며 각각의 x, y좌표 지점을 * 2를 해준다.
3. x1 ~ x2, y1 ~ y2를 순회하며 사각형의 내부라면 맵을 1로 초기화 해준다.
4. 만약 테두리의 값이 -1(기본값)이라면 해당 값을 0으로 변경해준다.
5. bfs함수의 매개변수로 캐릭터의 x, y좌표와 아이템의 x, y좌표에 2배를 하여 전달해 준다.
6. bfs함수의 리턴값을 바로 리턴 해주면 된다.

 

참고 사항

• 선분을 탐색해야 하기 때문에 길이 1짜리 선분을 길이 2인 선분으로 나누어 준다고 생각하면 된다.
• 길이가 2로 길어진 만큼 소요시간을 리턴 할때도 2로 나누어 출력해 주어야 한다.

 

정답 코드

#include <bits/stdc++.h>

using namespace std;
int v[101][101];
int lst[101][101];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

struct Pos {
    int x, y, t;
};

int bfs(int sx, int sy, int ex, int ey) {
    queue<Pos> q;
    q.push({sx, sy, 0});
    v[sx][sy] = 1;
    
    while (!q.empty()) {
        Pos pos = q.front(); q.pop();
        int cx = pos.x, cy = pos.y, ct = pos.t;
        if (cx == ex && cy == ey) return ct / 2;
        
        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i], ny = cy + dy[i], nt = ct + 1;
            if (0 <= nx && nx < 101 && 0 <= ny && ny < 101 && !v[nx][ny] && !lst[nx][ny]) {
                v[nx][ny] = 1;
                q.push({nx, ny, nt});
            }
        }
    }
    return -1;
}

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    memset(lst, -1, sizeof(lst));
    for (auto& r : rectangle) {
        int x1 = r[0] * 2, x2 = r[2] * 2;
        int y1 = r[1] * 2, y2 = r[3] * 2;
        for (int i = x1; i <= x2; i++) {
            for (int j = y1; j <= y2; j++) {
                if (x1 < i && i < x2 && y1 < j && j < y2) lst[i][j] = 1;
                else if (lst[i][j] == -1) lst[i][j] = 0;
            }
        }
    }
    
    return bfs(characterX * 2, characterY * 2, itemX * 2, itemY * 2);
}