백준 스터디 6주차 (2022-04-19 TUE ~ 2022-04-25 MON 📚)

🥈 2210번 - 숫자판 점프

❔ 문제 바로가기

⭐ 풀이의 핵심

숫자판의 i) 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 ii) 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 iii) 한 번 거쳤던 칸을 다시 거쳐도 되며, ...

i) (0,0)~(4,4) 모든 칸에 대해서 탐색 진행
ii) DFS로 depth가 5일 때까지 탐색
iii) visited check 필요 없음
+) 중복되는 숫자를 제외하기 위해 나오는 6자리 숫자를 unordered_set에 저장

🔽 코드 (C++)

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

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
vector<vector<int>> board(5, vector<int>(5));
unordered_set<int> availableNumbers; // 만들 수 있는 수들을 중복 없이 저장

bool isOutOfRange(int row, int col) {
    if (row < 0 || row >= 5 || col < 0 || col >= 5) {
        return true;
    }
    return false;
}

void search(int row, int col, int depth, int number) {
	// DFS
    if (depth == 5) { // depth가 5인 경우 만들어진 수 체크
        availableNumbers.insert(number);
        return;
    }

	// 인접해 있는 네 방향으로 이동 가능
    for (int i=0; i<4; i++) {
        int nextRow = row + dr[i];
        int nextCol = col + dc[i];

        if (isOutOfRange(nextRow, nextCol)) { continue; }
        search(nextRow, nextCol, depth+1, number*10+board[nextRow][nextCol]);
    }
}

int main() {
	// input
    for (int i=0; i<5; i++) {
        for (int j=0; j<5; j++) {
            scanf("%d", &board[i][j]);
        }
    }

	// solve
    for (int i=0; i<5; i++) {
        for (int j=0; j<5; j++) {
            search(i, j, 0, board[i][j]);
        }
    }

	// print
    printf("%d", availableNumbers.size());

    return 0;
}

🥇 2206번 - 벽 부수고 이동하기

❔ 문제 바로가기

⭐ 풀이의 핵심

(1,1) ~ (N,M)의 위치까지 이동하려 하는데, 이때 i) 최단 경로로 이동하려 한다. ... 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개까지 부수고 이동하여도 된다. ...

i) BFS 활용
ii) 벽을 부술 수 있는 기회가 있는지 체크하는 chance 변수 필요 + visited를 두 가지 경우 (벽을 깬 상태의 방문 여부 vs 벽을 깨지 않은 상태의 방문 여부)로 나누어 체크

• 이동 ❌
  • 이동할 수 있는 곳(0)이고 방문한 경우
  • 이동할 수 없는 벽(1)이고 벽을 부술 수 있는 기회가 없는 경우
• 이동 ⭕
  • 이동할 수 있는 곳(0)이고 방문하지 않은 경우
  • 이동할 수 없는 벽(1)이고 벽을 부술 수 있는 기회가 있는 경우

🔽 코드 (C++)

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

struct Info {
    int row;
    int col;
    int count;
    int chance;
};

int N;
int M;
vector<vector<int>> map(1000, vector<int>(1000, -1));
vector<vector<vector<bool>>> visited(1000, vector<vector<bool>>(1000, vector<bool>(2, false))); 
// cf. visited[][][0]: 벽을 깬 상태의 방문 여부 vs visited[][][1]: 벽을 깨지 않은 상태의 방문 여부

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

bool isOutOfRange(int row, int col) {
    if (row < 0 || row >= N || col < 0 || col >= M) {
        return true;
    }
    return false;
}

int bfs() {
	// BFS
    queue<Info> q;
    q.push({0, 0, 1, 1});
    visited[0][0][1] = true; // cf. visited[row][col][chance]

    while (!q.empty()) {
        int qSize = q.size();
        for (int i=0; i<qSize; i++) {
            Info curr = q.front();
            q.pop();
            
           	// (N,M)에 도달한 경우 curr.count 리턴
            if (curr.row == N-1 && curr.col == M-1) {
                return curr.count;
            }
            
            for (int j=0; j<4; j++) {
                int nextRow = curr.row + dr[j];
                int nextCol = curr.col + dc[j];

                if (isOutOfRange(nextRow, nextCol)) { continue; }
                
                // (nextRow, nextCol) 위치가 이동할 수 있는 곳이고 현재의 상태에서 아직 방문하지 않은 경우
                if (map[nextRow][nextCol] == 0 && !visited[nextRow][nextCol][curr.chance]) {
                    q.push({nextRow, nextCol, curr.count+1, curr.chance});
                    // 현재 상태의 visited check 벡터 활용
                    visited[nextRow][nextCol][curr.chance] = true;
                }
                
                // (nextRow, nextCol) 위치가 이동할 수 없는 벽이고 벽을 부술 수 있는 기회가 남아 있는 경우
                else if (map[nextRow][nextCol] == 1 && curr.chance) {
                    q.push({nextRow, nextCol, curr.count+1, curr.chance-1});
                    // 벽을 깬 상태의 visited check 벡터 활용
                    visited[nextRow][nextCol][curr.chance-1] = true;
                }
            }
        }
    }

	// 불가능할 때는 -1 출력
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;
    
    // 입력 받는 같은 줄에 있는 숫자들 사이에 공백이 없으므로
    // string으로 입력받고 split할 것
    // 또는 map을 아예 vector<string> map으로 선언
    string oneLine;
    for (int i=0; i<N; i++) {
        cin >> oneLine;
        for (int j=0; j<M; j++) {
            map[i][j] = oneLine[j] - '0';
        }
    }

    cout << bfs();

    return 0;
}