[백준 BOJ] 1074번 1063번 (C++) | 백준 스터디 4주차

백준 스터디 4주차 (2022-04-05 TUE ~ 2022-04-11 MON 📚)

🥈 1074번 - Z

❔ 문제 바로가기

⭐ 풀이의 핵심

Divide And Conquer 분할정복 + Recursion 재귀

• A -> B -> C -> D 사분면 순으로 탐색
• 현재 해당 사분면에 찾고자 하는 좌표가 존재할 경우
  👉 좌표를 찾을 때까지 4분면으로 쪼개는 작업을 계속 반복하기
• 존재하지 않을 경우
  👉 해당 사분면에 있는 칸의 개수를 한 번에 더하고 다음 사분면으로 넘어가기

🔽 코드 (C++)

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

int N, r, c;
int answer;

void drawZ(int row, int col, int powN) { // {row, col}은 현재 사분면의 탐색 시작점
    if (row == r && col == c) {
        printf("%d", answer);
        return;
    }
    
    // {r, c}가 현재 사분면에 없는 경우
    // 현재 사분면을 한 칸씩 탐색해볼 필요 없음
    if (r < row || r >= row+powN || c < col || c >= col+powN) {
        answer += powN * powN;
        return;
    }

    // {r, c}가 현재 사분면에 있는 경우
    // 현재 사분면을 재귀적으로 분할하여 탐색
    int halfPowN = powN / 2; // powN이 2^N이라면 halfPowN은 2^(N-1)
    drawZ(row, col, halfPowN);
    drawZ(row, col+halfPowN, halfPowN);
    drawZ(row+halfPowN, col, halfPowN);
    drawZ(row+halfPowN, col+halfPowN, powN);    
}

int main() {
    scanf("%d %d %d", &N, &r, &c);
    drawZ(0, 0, pow(2, N));

    return 0;
}

🥈 1063번 - 킹

❔ 문제 바로가기

⭐ 풀이의 핵심

R : 한 칸 오른쪽으로
L : 한 칸 왼쪽으로
B : 한 칸 아래로
T : 한 칸 위로
RT : 오른쪽 위 대각선으로
LT : 왼쪽 위 대각선으로
RB : 오른쪽 아래 대각선으로
LB : 왼쪽 아래 대각선으로

---

👉 킹이 움직일 수 있는 8가지 방향을 담은 dr(direction row), dc(direction col) 배열 선언

• 문제에서 행의 가장 아래는 1이고 가장 위는 8
  👉 우리가 기존에 알고 있는 행렬의 인덱스와 반대인 점을 주의하여 배열 선언
  ex) RT : 오른쪽 위 대각선으로의 dc 값은 1, dr 값은 -1이 아니라 1

• 문제에서 열의 경우 가장 왼쪽은 A, 가장 오른쪽은 H와 같이 알파벳으로 표시되어 있음
  👉 행의 값을 정수로 저장하고자 할 때 행의 값에 (해당하는 알파벳 - 'A' + 1)을 통해 알파벳 A가 1을 가리킬 수 있도록 저장

🚨 행렬 순서 또한 반대로 되어있음.. 실수 주의!
ex) A2는 1행 2열이 아니라 1열 2행을 의미

🔽 코드 (C++)

#include <iostream>
#include <string>

using namespace std;

#define MAX_IDX 8

// R L B T RT LT RB LB
int dr[8] = {0, 0, -1, 1, 1, 1, -1, -1};
int dc[8] = {1, -1, 0, 0, 1, -1, 1, -1};

// 열은 가장 왼쪽 A~오른쪽 H, 행은 가장 아래 1~위 8
// {row, col}
pair<int, int> kingPos;
pair<int, int> stonePos;

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

void move(string cmd) {
    int flag;
    if (cmd == "R") { flag = 0; }
    else if (cmd == "L") { flag = 1; }
    else if (cmd == "B") { flag = 2; }
    else if (cmd == "T") { flag = 3; }
    else if (cmd == "RT") { flag = 4; }
    else if (cmd == "LT") { flag = 5; }
    else if (cmd == "RB") { flag = 6; }
    else if (cmd == "LB") { flag = 7;}

    int nextRow = kingPos.first + dr[flag];
    int nextCol = kingPos.second + dc[flag];

    // 킹이 체스판 밖으로 나갈 경우에는 그 이동은 건너 뛰고 다음 이동을 한다.
    if (isOutOfRange(nextRow, nextCol)) { return; }

    // 돌과 같은 곳으로 이동할 때는, 돌을 킹이 움직인 방향과 같은 방향으로 한 칸 이동시킨다.
    if (nextRow == stonePos.first && nextCol == stonePos.second) {
        int nextStoneRow = stonePos.first + dr[flag];
        int nextStoneCol = stonePos.second + dc[flag];

        // 돌이 체스판 밖으로 나갈 경우에는 그 이동은 건너 뛰고 다음 이동을 한다.
        if (isOutOfRange(nextStoneRow, nextStoneCol)) { return; }

        stonePos.first = nextStoneRow;
        stonePos.second = nextStoneCol;
    }
    
    kingPos.first = nextRow;
    kingPos.second = nextCol;
}

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

    // 알파벳은 열을 상징하고, 숫자는 행을 상징
    string king, stone;
    int N;
    cin >> king >> stone >> N;

    kingPos.first = king[1] - '0';
    kingPos.second = king[0] - 'A' + 1;
    stonePos.first = stone[1] - '0';
    stonePos.second = stone[0] - 'A' + 1;
    
    string cmd;
    for (int i=0; i<N; i++) {
        cin >> cmd;
        move(cmd);
    }

    char kingCol = kingPos.second - 1 + 'A';
    char stoneCol = stonePos.second - 1 + 'A';
    cout << kingCol << kingPos.first << "\n";
    cout << stoneCol << stonePos.first << "\n";
    
    return 0;
}