๐Ÿ“ Coding Test Study/Algorithm Problem

[C++][Baekjoon] 14503๋ฒˆ ๋กœ๋ด‡ ์ฒญ์†Œ๊ธฐ

ibelieveinme 2021. 8. 22. 16:52
728x90

๋ฌธ์ œ

https://www.acmicpc.net/problem/14503

 

14503๋ฒˆ: ๋กœ๋ด‡ ์ฒญ์†Œ๊ธฐ

๋กœ๋ด‡ ์ฒญ์†Œ๊ธฐ๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ฒญ์†Œํ•˜๋Š” ์˜์—ญ์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ๋กœ๋ด‡ ์ฒญ์†Œ๊ธฐ๊ฐ€ ์žˆ๋Š” ์žฅ์†Œ๋Š” N×M ํฌ๊ธฐ์˜ ์ง์‚ฌ๊ฐํ˜•์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ์œผ๋ฉฐ, 1×1ํฌ๊ธฐ์˜ ์ •์‚ฌ๊ฐํ˜• ์นธ์œผ๋กœ ๋‚˜๋ˆ„์–ด

www.acmicpc.net

 

์ฝ”๋“œ

#include <iostream>
using namespace std;

void CleanArea(int, int, int);

const int direction[4][2] = { {-1,0},{0,1},{1,0},{0,-1} }; //๋ถ, ๋™, ๋‚จ, ์„œ
int map[51][51];
int height, width;
int clean_count;

int main() {
    cin >> height >> width;

    int robot_x = 0, robot_y = 0, robot_direction = 0;
    cin >> robot_x >> robot_y >> robot_direction;
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            cin >> map[y][x];
        }
    }
    CleanArea(robot_x, robot_y, robot_direction);
    cout << clean_count;
}

void CleanArea(int robot_x, int robot_y, int robot_direction) {
    //1. ํ˜„์žฌ ์œ„์น˜๋ฅผ ์ฒญ์†Œํ•œ๋‹ค.
    if (map[robot_x][robot_y] == 0) {
        map[robot_x][robot_y] = 2;
        clean_count += 1;
    }
    //2. ํ˜„์žฌ ์œ„์น˜์—์„œ ํ˜„์žฌ ๋ฐฉํ–ฅ์„ ๊ธฐ์ค€์œผ๋กœ ์™ผ์ชฝ๋ฐฉํ–ฅ๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ํƒ์ƒ‰์„ ์ง„ํ–‰ํ•œ๋‹ค.
    for (int i = 0; i < 4; i++) {
        robot_direction = (robot_direction + 3) % 4;

        int next_x = robot_x + direction[robot_direction][0];
        int next_y = robot_y + direction[robot_direction][1];

        //a. ์™ผ์ชฝ ๋ฐฉํ–ฅ์— ์•„์ง ์ฒญ์†Œํ•˜์ง€ ์•Š์€ ๊ณต๊ฐ„์ด ์กด์žฌํ•œ๋‹ค๋ฉด, ๊ทธ ๋ฐฉํ–ฅ์œผ๋กœ ํšŒ์ „ํ•œ ๋‹ค์Œ ํ•œ ์นธ์„ ์ „์ง„ํ•˜๊ณ  1๋ฒˆ๋ถ€ํ„ฐ ์ง„ํ–‰ํ•œ๋‹ค.
        if (map[next_x][next_y] == 0) {
            CleanArea(next_x, next_y, robot_direction);
            return; //โ˜…โ˜…โ˜…๋Œ์•„์™€์„œ ๋˜ ์ƒํ•˜์ขŒ์šฐ๋ฅผ ๋ณด๋Š”๊ฒŒ ์•„๋‹ˆ๋ผ ๋น ์ ธ๋‚˜์™€์•ผ ํ•จ
        }//b. ์™ผ์ชฝ ๋ฐฉํ–ฅ์— ์ฒญ์†Œํ•  ๊ณต๊ฐ„์ด ์—†๋‹ค๋ฉด, ๊ทธ ๋ฐฉํ–ฅ์œผ๋กœ ํšŒ์ „ํ•˜๊ณ  2๋ฒˆ์œผ๋กœ ๋Œ์•„๊ฐ„๋‹ค.
    }
    //c. ๋„ค ๋ฐฉํ–ฅ ๋ชจ๋‘ ์ฒญ์†Œ๊ฐ€ ์ด๋ฏธ ๋˜์–ด์žˆ๊ฑฐ๋‚˜ ๋ฒฝ์ธ ๊ฒฝ์šฐ์—๋Š” ๋ฐ”๋ผ๋ณด๋Š” ๋ฐฉํ–ฅ์„ ์œ ์ง€ํ•œ ์ฑ„๋กœ ํ•œ ์นธ ํ›„์ง„์„ ํ•˜๊ณ  2๋ฒˆ์œผ๋กœ ๋Œ์•„๊ฐ„๋‹ค.
    int back_x = robot_x - direction[robot_direction][0];
    int back_y = robot_y - direction[robot_direction][1];

    if (map[back_x][back_y] != 1) {
        CleanArea(back_x, back_y, robot_direction);
    }
    //d. ๋„ค ๋ฐฉํ–ฅ ๋ชจ๋‘ ์ฒญ์†Œ๊ฐ€ ์ด๋ฏธ ๋˜์–ด์žˆ๊ฑฐ๋‚˜ ๋ฒฝ์ด๋ฉด์„œ, ๋’ค์ชฝ ๋ฐฉํ–ฅ์ด ๋ฒฝ์ด๋ผ ํ›„์ง„๋„ ํ•  ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ์—๋Š” ์ž‘๋™์„ ๋ฉˆ์ถ˜๋‹ค.
    return;
}
728x90