[백준 BOJ] 15559번 - 내 선물을 받아줘 (C++)

교공 알고리즘 스터디 24주차 탐색문제

15559번: 내 선물을 받아줘 | 문제 바로가기

문제풀이 (2022-02-22 TUE 💻)

⭐ 풀이의 핵심

아직 방문하지 않은 모든 칸에 대하여
dfs와 유사하게 재귀를 활용해 지도에 쓰여 있는 대로 이동한다
아래와 같은 사항들에 유의하며 visited check를 하고 선물을 놓는다

• 다음 칸이 아직 방문하지 않은 칸일 경우 재귀 호출을 통해 탐색을 계속
• 다음 칸이 이미 방문한 칸일 경우
  • 해당 칸이 이번 회차의 탐색에서 방문한 칸일 경우
    cycle이 형성되었음을 의미, 선물을 놓음!
  • 이전 회차의 탐색에서 이미 방문한 칸(경로) 수렴한 경우
    이미 해당 경로에는 선물이 놓여 있으므로 선물을 놓지 않고 종료

👉 visited 벡터를 bool형이 아닌 int형으로 선언하여
탐색 회차마다 visited 벡터에 저장할 값을 다르게 해주어
이미 방문한 칸을 마주쳤을 때 visited에 저장된 값을 비교하여
선물을 놓을지 말지 결정할 수 있도록 한다
처음에는 경로의 개수 == 놓아야 하는 선물의 개수 라고 생각했는데 아니었다

👉 추가로 아래의 조건이 존재하므로 이동 탐색 시 range check는 따로 해줄 필요가 없다

지도에 쓰여 있는대로 이동했을 때, 지도를 벗어나는 경우는 없다.

🔽 코드 (C++)

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

int N, M;
int gift;
vector<vector<char>> map(1000, vector<char>(1000));
vector<vector<int>> visited(1000, vector<int>(1000));

// North West East South
int dr[4] = {-1, 0, 0, 1};
int dc[4] = {0, -1, 1, 0};

int getDir(char c) {
    if (c == 'N') { return 0; }
    else if (c == 'W') { return 1; }
    else if ( c == 'E') { return 2; }
    else { return 3; } // c == 'S'
}

void move(int r, int c, int pathId) {
    // dfs
    visited[r][c] = pathId;

    int dir = getDir(map[r][c]);
    int nr = r + dr[dir];
    int nc = c + dc[dir];

    if (visited[nr][nc] == 0) {
        // 아직 방문하지 않은 칸일 경우
        move(nr, nc, pathId);
    }
    else if (visited[nr][nc] == pathId) {
        // 이번에 탐색한 이동 경로에서 이미 방문한 칸일 경우 (사이클 형성)
        gift++;
    }
}

void solve() {      
    int pathId = 0;
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            if (visited[i][j] == 0) {
                pathId++;
                move(i, j, pathId);
            }
        }
    }
}

int main() {
    scanf("%d %d", &N, &M);
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            scanf(" %c", &map[i][j]);
        }
    }

    solve();
    printf("%d", gift);

    return 0;
}

스터디 (2022-02-27 SUN 📚)

대부분 비슷한 방법으로 풀어와서 특별히 복기할 내용이 없었다 💬