728x90

문제

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.

1번 2번 3번 4번 5번

1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 # 6 0
0 0 0 0 0 0
 
0 0 0 0 0 0
0 0 0 0 0 0
# # 1 0 6 0
0 0 0 0 0 0
 
0 0 # 0 0 0
0 0 # 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0
 
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 # 0 0 0
→ ← ↑ ↓

CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 칸을 감시할 수 없다.

0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 5

위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.

0 0 0 0 0 #
# 2 # # # #
0 0 0 0 6 #
0 6 # # 2 #
0 0 0 0 0 #
# # # # # 5
 
0 0 0 0 0 #
# 2 # # # #
0 0 0 0 6 #
0 6 0 0 2 #
0 0 0 0 # #
# # # # # 5
 
0 # 0 0 0 #
0 2 0 0 0 #
0 # 0 0 6 #
0 6 # # 2 #
0 0 0 0 0 #
# # # # # 5
 
0 # 0 0 0 #
0 2 0 0 0 #
0 # 0 0 6 #
0 6 0 0 2 #
0 0 0 0 # #
# # # # # 5
왼쪽 상단 2: ↔, 오른쪽 하단 2: ↔ 왼쪽 상단 2: ↔, 오른쪽 하단 2: ↕ 왼쪽 상단 2: ↕, 오른쪽 하단 2: ↔ 왼쪽 상단 2: ↕, 오른쪽 하단 2: ↕

CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.

0 0 2 0 3
0 6 0 0 0
0 0 6 6 0
0 0 0 0 0

위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.

# # 2 # 3
0 6 # 0 #
0 0 6 6 #
0 0 0 0 #

사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. 

CCTV의 최대 개수는 8개를 넘지 않는다.

출력

첫째 줄에 사각 지대의 최소 크기를 출력한다.

첫 번째 풀이 방법(시간 초과)

0. dfs() 호출

1. map[i][j]을 temp[i][j]에 복사

2. map[i][j] 변경

3. 조건 충족 후 temp[i][j]로 되돌리기.

이때 map[i][j] == 1,2,3,4,5 일 때 모두 배열의 복사, 되돌리기 진행,--> 시간 초과

 

두 번째 풀이 방법(정답)

0. dfs() 호출

1. 동서남북 네 가지 방향에 대한 반복문 안에서 감시범위 체크, dfs(), 다시 되돌리기 함수 실행

2. visited[][] 배열에 감시카메라가 닿는 모든 칸에 +1

3. dfs(depth + 1) 호출

4. visited[][] 배열에 감시카메라가 닿는 모든 칸에 -1

5. depth == (1~5)의 개수 일 때 visited[][]의 0의 개수 비교

*주의사항 dx dy를 시계방향, 반시계 방향 순서대로 정의해야 한다.

예를 들어 좌우상하라고 설정하면

2번 케이스일 때 (좌우)(우상)(상하)(하좌) 이런 식으로 방향이 틀려지게 된다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 8
using namespace std;
int n, m;
int map[MAX][MAX], visited[MAX][MAX];
//하, 좌, 상, 우
int dx[] = { 0, -1, 0, 1 };
int dy[] = { 1, 0, -1, 0 };
struct pos {
    int y, x;
};
vector<pos> v;
int ans = 1e9;
void check(int y, int x, int dir, int num)
{
    int ny = y;
    int nx = x;
    while (true)
    {
        ny += dy[dir];
        nx += dx[dir];
        if (map[ny][nx] == 6)
            break;
        if (ny >= 0 && nx >= 0 && ny < n && nx < m)
            visited[ny][nx] += num;
        else
            break;
    }
}
void rotate(int depth, int i, int num)
{
    int y = v[depth].y;
    int x = v[depth].x;
    int number = map[y][x];
    switch (number)
    {
    case 1:
        check(y, x, (i + 3) % 4, num);
        break;
    case 2:
        check(y, x, (i + 1) % 4, num);
        check(y, x, (i + 3) % 4, num);
        break;
    case 3:
        check(y, x, (i + 2) % 4, num);
        check(y, x, (i + 3) % 4, num);
        break;
    case 4:
        check(y, x, (i + 1) % 4, num);
        check(y, x, (i + 2) % 4, num);
        check(y, x, (i + 3) % 4, num);
        break;
    case 5:
        check(y, x, (i + 0) % 4, num);
        check(y, x, (i + 1) % 4, num);
        check(y, x, (i + 2) % 4, num);
        check(y, x, (i + 3) % 4, num);
        break;
    }
}
void solve(int depth)
{
    if (depth == v.size())
    {
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (visited[i][j] == 0)
                    cnt++;
            }
        }
        ans = min(ans, cnt);
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        rotate(depth, i, 1);
        solve(depth + 1);
        rotate(depth, i, -1);
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> map[i][j];
            if (map[i][j] != 0 && map[i][j] != 6)
            {
                v.push_back({ i,j });
                visited[i][j] = map[i][j];
            }
            if (map[i][j] == 6)
                visited[i][j] = 6;
        }
    }
    solve(0);
    cout << ans;
    return 0;
}
 cs

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

 

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감

www.acmicpc.net

 

LIST
저작자표시 비영리 변경금지 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

[구현 BOJ-15685] 드래곤 커브, c++  (1) 2021.08.09
[구현, BOJ-15684] 사다리 조작, c++  (1) 2021.08.09
[구현, BOJ-14891] 톱니바퀴, c++  (0) 2021.05.25
[시뮬레이션, BOJ-14503 ] 로봇청소기, c++  (0) 2021.05.20
[구현, BOJ-14500] 테트로미노, c++  (0) 2021.05.13
728x90

로봇 청소기 

문제

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.

로봇 청소기는 다음과 같이 작동한다.

  1. 현재 위치를 청소한다.
  2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
    1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
    2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
    3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
    4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

입력

첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 50)

둘째 줄에 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.

셋째 줄부터 N개의 줄에 장소의 상태가 북쪽부터 남쪽 순서대로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 빈 칸은 0, 벽은 1로 주어진다. 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다.

로봇 청소기가 있는 칸의 상태는 항상 빈 칸이다.

출력

로봇 청소기가 청소하는 칸의 개수를 출력한다.

이 문제에서 고려해야할 요소는 map[y][x] == 0 이면 출력 변수 ++ 해주고, 

다음 방향 탐색 -> 4방향 모두 막혀 있으면 뒤로 이동, 이때 뒤에가 벽이면 멈춘다.

그래서 for(int i=0;i< 4;i++){} 구문에 탐색하는 코드를 넣어 탐색에 실패했을경우 문제의 2.3에 해당하는지 2.4에 해당하는지 확인해 준다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/* 로봇 청소기 영역의 개수를 구하는 프로그램 */
//n x m 영역 빈칸 or 벽
//방향 : 동 서 남 북
//로봇청소기 루틴
// 1. 현재 위치 청소
// 2. 현재위치에서 왼쪽방향부터 탐색
//   a. 왼쪽 방향이 청소하지 않았으면 그방향으로 전진 -> 1
//   b. 왼쪽 방향에 청소할 공간이 없으면, 그 방향 회전 -> 2
//   c. 네 방향 모두 청소가 이미 되어있거나 벽이면, 바라보는 방향 유지한 채로 후진 -> 2
//   d. 네 방향 모두 청소가 이미 되어있거나 벽이면서 뒤쪽방향도 벽이면 멈춤
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n, m;
int input[50][50];
int y, x;
int ans;
int dir;
//북 동 남 서
int dx[] = { 0, 1, 0, -1 };
int dy[] = { -1, 0, 1, 0 };
 
int left_dir(int d)
{
    if (d == 0)
    {
        return 3;
    }
    else if (d == 1)
    {
        return 0;
    }
    else if (d == 2)
    {
        return 1;
    }
    else
        return 2;
}
void solve()
{
    while (true)
    {
        if (input[y][x] == 0)
        {
            input[y][x] = 2;
            ans++;
        }
        bool nextClean = false;
        for (int i = 0; i < 4; i++)
        {
            dir = left_dir(dir);
            int ny = y + dy[dir];
            int nx = x + dx[dir];
 
            if (input[ny][nx] == 0)
            {
                x = nx;
                y = ny;
                nextClean = true;
                break;
            }
        }
        if (nextClean) continue;
        //뒤
        int back_d = left_dir(left_dir(dir));
        y = y + dy[back_d];
        x = x + dx[back_d];
 
        if (input[y][x] == 1)
            break;
    }
}
int main()
{
    cin >> n >> m;
 
    //입력 y, x, 바라보는 방향 d
    //d = 0 : 북 // d = 1 : 동 // d = 2 : 남 // d = 3 : 서
    cin >> y >> x >> dir;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> input[i][j];
        }
    }
    solve();
    cout << ans;
    return 0;
}
 cs
LIST
저작자표시 비영리 변경금지 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

[시뮬레이션, BOJ-15683]감시, c++  (0) 2021.06.04
[구현, BOJ-14891] 톱니바퀴, c++  (0) 2021.05.25
[구현, BOJ-14500] 테트로미노, c++  (0) 2021.05.13
[simulation, BOJ-14499] 주사위 굴리기, c+  (0) 2021.05.12
[mathmatics BOJ-13458] 시험감독, c++  (1) 2021.05.11

+ Recent posts

티스토리툴바