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

 

2468번: 안전 영역

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어

www.acmicpc.net

안전 영역을 구해줄 것이므로 물에 잠기지 않는 부분에 대해서 BFS를 해준다.

그리고 BFS를 한 횟수가 안전영역의 수가 된다.

 

 

지역의 높이 범위가 1부터 100인데 시간을 줄이기 위해서 지역의 정보를 처음에 입력을 받을 때 지역 높이의 최댓값을 구해놓는다.

그리고 1부터 높이의 최댓값 -1 까지만큼 비가 오는 경우를 모두 구해주면 된다.

높이의 최댓값 이상으로 비가 오는 경우는 안전 영역이 0이 되기 때문이다.

그리고 각 경우에서의 안전 영역을 정답(최댓값)과 비교해서 저장한다.

 

주의할 점은 

아무 지역도 물에 잠기지 않을 수도 있다.

라고 문제 밑부분 노트에 쓰여있는데 이 경우는 안전 영역이 1이므로 정답의 초기값은 0이 아닌 1로 해놓아야 한다.

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
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int n;
int maxh;
int ans;
int map[100][100];
bool check[100][100];
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
void bfs(int x, int y, int h) {
 
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    check[x][y] = true;
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            if (check[nx][ny]) continue;
            if (map[nx][ny] <= h) continue;
 
            q.push(make_pair(nx, ny));
            check[nx][ny] = true;
        }
    }
 
}
 
void solve() {
 
 
    for (int h = 1; h < maxh; h++) {
        memset(check, false, sizeof(check));
        int safearea = 0;
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (check[i][j]) continue;
                //높이가 더 낮은 곳은 물에 잠기므로 넘어간다
                if (map[i][j] <= h) continue;
 
                bfs(i, j, h);
                safearea++;
            }
        }
 
        if (ans < safearea) ans = safearea;
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            if (maxh < map[i][j]) maxh = map[i][j];
        }
    }
 
 
    ans = 1;
    
    solve();
    cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter
  

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 17143. 낚시왕  (0) 2019.08.18
[BOJ] 17406. 배열 돌리기 4  (0) 2019.08.13
[BOJ] 2573. 빙산  (0) 2019.08.13
[BOJ] 2234. 성곽  (0) 2019.08.13
[BOJ] 11559. Puyo Puyo  (0) 2019.08.08

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

 

2573번: 빙산

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지

www.acmicpc.net

BFS를 이용해서 푸는 문제이다.

 

인접한 칸이 바다인 경우에는 그 개수를 세주어서 빙산의 높이에서 빼주면 된다.

바다가 아닌 빙산인 경우에는 큐에 넣어주고 해당 빙산에 대해서도 탐색을 이어가면 된다.

 

 

BFS는 연결된 모든 칸을 방문하기 때문에 연결되지 않은 칸에 방문하기 위해서는 BFS를 새로 시작하여야 한다.

즉, bfs횟수가 1회일 때는 아직 모두 연결되어 있는 한 덩어리라는 뜻이므로 계속 시간을 늘려가며 bfs를 진행하고

BFS 횟수가 1번이 넘을 때는 빙산이 두 덩어리 이상이 됐음을 의미하므로 그때 시간을 출력해주고 탐색을 종료한다.

 

 

만약 다 녹았는데 빙산이 분리되지 않은 경우를 처리하기 위해서는 flag 변수를 둬서 bfs탐색이 한 번도 일어나지 않은 경우에 0을 출력해주고 종료하도록 해줬다.

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
107
108
109
110
111
112
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int n, m;
int map[300][300];
bool check[300][300];
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    check[x][y] = true;
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        int cnt = 0;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            
            if (check[nx][ny]) continue;
 
            //인접한 칸이 바다인 경우 cnt증가
            if (map[nx][ny] == 0) {
                cnt++;
            }
            else {
                //빙산인 경우에는 큐에 넣어주고 계속 탐색
                q.push(make_pair(nx, ny));
                check[nx][ny] = true;
            }
            
        }
 
 
        //인접해 있는 바다의 수만큼 높이 줄어든다.
        map[x][y] -= cnt;
        //0보다 작아지지는 않는다.
        if (map[x][y] < 0) map[x][y] = 0;
 
    }
 
}
 
void solve() {
 
    int time = 0;
    while (true) {
        int cnt = 0;
        bool flag = false;
        for (int i = 1; i < n - 1; i++) {
            for (int j = 1; j < m - 1; j++) {
                //바다인 경우 continue
                if (map[i][j] == 0) continue;
                //이미 방문한 경우
                if (check[i][j]) continue;
 
                //빙산이 아직 있다.
                flag = true;
                bfs(i, j);
 
                //빙산의 덩어리 수
                cnt++;
            }
        }
 
        //전부 다 녹을 때까지 두덩어리 이상으로 분리되지 않는 경우
        if (!flag) {
            cout << 0 << '\n';
            return;
        }
 
 
        //두 덩어리 이상이 되었을 경우 시간을 출력하고 return(종료)
        if (cnt > 1) {
            cout << time << "\n";
            return;
        }
 
 
        //시간 증가
        time++;
 
        memset(check, false, sizeof(check));
    }
 
    
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
 
    solve();
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 17406. 배열 돌리기 4  (0) 2019.08.13
[BOJ] 2468. 안전 영역  (0) 2019.08.13
[BOJ] 2234. 성곽  (0) 2019.08.13
[BOJ] 11559. Puyo Puyo  (0) 2019.08.08
[BOJ] 3190. 뱀  (0) 2019.08.06

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

 

2234번: 성곽

문제 대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오. 이 성에 있는 방의 개수 가장 넓은 방의 넓이 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기 위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을

www.acmicpc.net

  1. 이 성에 있는 방의 개수
  2. 가장 넓은 방의 넓이
  3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

를 구하는 문제이다. 이 문제는 bfs와 비트 마스크를 사용해서 풀었다.

 

 

먼저 1번과 2번문제에 대한 답을 먼저 구하였다.

방문하지 않은 모든 칸에 bfs를 사용하여 방문하고 bfs가 시작될 때마다(새로운 방이므로) 방 개수를 늘려준다.

그리고 bfs탐색을 할때마다 방문하는 칸의 개수를 세줘서 방의 넓이를 구하여 방의 넓이 중 최댓값을 구할 수 있다.

 

이 문제에서 bfs를 할 때 중요한 부분은 벽인지 아닌지 알아내야 한다.

 

 

벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 참고로 이진수의 각 비트를 생각하면 쉽다. 따라서 이 값은 0부터 15까지의 범위 안에 있다.

라고 문제 입력에서 주어지는데 이 부분이 힌트인 것 같다. 그림으로 나타내면 아래와 같다.

 

 

 

 

문제에서 주어진 예시 그림(맨 위 그림)의 왼쪽 끝칸(0,0)을 예시로 들어보면 아래 그림과 같다. 서쪽, 북쪽, 남쪽에 벽이 있기 때문에

1+2+8 = 11로 11이 문제 입력에서 주어진다. 11은 다시 이진수로 1011로 나타낼 수 있으므로 이를 이용해서 비트 마스크로 검사를 한다.

int dx[] = { 0,-1,0,1 };

int dy[] = { -1,0,1,0 };

먼저 방향 배열을 서, 북, 동, 남 순서로 해놓아야 한다. 그래야 1 << 0을 했을 때의 값이 1이므로 서쪽을 표현할 수 있고 1<<1 은 2로 북쪽을 표현할 수 있다.

그리고 검사할 칸과 & (1<<k)를 해서 해당 위치에 1을 가지고 있는지 검사한다. (k는 0부터 3으로 네 방향의 index)

1을 가지고 있는 경우(위의 연산 결과가 0이 아닌 경우)에는 벽이므로 해당 방향으로는 이동하지 않는다.

 

 

그리고 나중에 3번 문제를 해결하기 위해서플러드 필 알고리즘(연결 요소에 번호를 매김)을 사용한다. bfs를 할 때 현재 연결된 칸들에 방 번호를 매겨주고 각 방의 넓이 또한 cnt 배열에 저장해놓는다.

 

 

3번 문제를 해결하기 위해서는 다음과 같은 생각을 했다.

인접해있는 방과 현재 방의 넓이를 합쳤을 때의 최댓값이 하나의 벽을 제거했을 때의 결과와 마찬가지다.

아래 그림을 봤을 때 1번 방은 2번 방과 3번 방과 인접해있는데 3번 방과 인접해있는 벽 중 하나를 제거했을 때 최댓값을 얻을 수 있다.

 

 

코드로 구현하자면 다시 새로운 bfs를 이용한다. 이때 bfs에서는 아까 플러드 필 알고리즘을 사용하여 방 번호를 매긴 배열을 이용한다.

이동했을 때 같은 방인 경우에는 계속 큐에 넣고 방문 체크를 해주며 탐색을 이어가고 같은 방이 아닌 경우에는 현재 방의 칸수와 옆의 방의 칸수를 합친 값(위에서 저장한 cnt배열을 이용)을 저장하고 이 합쳐진 값들 중 최댓값이 정답이 된다.

 

1번 방에 대해 인접한 방에 대해서 모두 탐색을 해봤다면 다음 2번 방을 검사할 때는 다시 1번 방과 비교할 필요는 없다.

그러므로 bfs로 방문한 칸은 모두 다 체크해주면 된다.

 

 

역시 코드를 보는 게 가장 이해하기 쉬울 것 같다ㅎㅎ

순서는 main -> solve -> bfs 다음에 removeWall -> bfs2로 진행된다.

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int m, n;
int map[50][50];
int visit[50][50];
bool check[50][50];
int cnt[2500];
 
 
int dx[] = { 0,-1,0,1 };
int dy[] = { -1,0,1,0 };
 
int bfs2(int x, int y) {
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    check[x][y] = true;
 
    int sum = 0;
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (check[nx][ny]) continue;
 
 
            //같은 방이면 큐에 넣고
            if (visit[nx][ny] == visit[x][y]) {
                q.push(make_pair(nx, ny));
                check[nx][ny] = true;
            }
            else { //다른 방이면 그 방과 합쳐졌을 때의 넓이를 저장
                int tmp = cnt[visit[x][y]] + cnt[visit[nx][ny]];
                if (sum < tmp) sum = tmp;
            }
 
        }
    }
 
    return sum;
 
}
 
void removeWall() {
    queue<pair<int, int>> q;
 
    int sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (check[i][j]) continue;
            int tmp = bfs2(i, j);
            if (sum < tmp) sum = tmp;
        }
    }
    
    cout << sum << '\n';
}
 
int bfs(int x, int y, int num) {
    int cnt = 1;
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    visit[x][y] = num;
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            //해당 방향이 벽인 경우
            if (map[x][y] & (1 << k)) continue;
 
            int nx = x + dx[k];
            int ny = y + dy[k];
 
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (visit[nx][ny]) continue;
 
            q.push(make_pair(nx, ny));
 
            //방 번호를 기록
            visit[nx][ny] = num;
            cnt++;
        }
 
    }
 
 
    //연결된 칸의 개수를 리턴(방의 넓이)
    return cnt;
}
 
void solve() {
 
    int maxcnt = 0;
    int roomcnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (visit[i][j]) continue;
 
            //bfs출발할 때마다 방의 개수 늘어난다
            int tmp = bfs(i, j, ++roomcnt);
 
            //방 별로 넓이를 저장해놓는다.
            cnt[roomcnt] = tmp;
 
            //가장 넓은 방의 넓이
            if (maxcnt < tmp) maxcnt = tmp;
        }
    }
 
    //1번 답 출력
    cout << roomcnt << "\n";
 
    //2번 답 출력
    cout << maxcnt << "\n";
 
 
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> m >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
 
    //1번과 2번 답을 구한다
    solve();
 
    //3번 답을 구한다
    removeWall();
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2468. 안전 영역  (0) 2019.08.13
[BOJ] 2573. 빙산  (0) 2019.08.13
[BOJ] 11559. Puyo Puyo  (0) 2019.08.08
[BOJ] 3190. 뱀  (0) 2019.08.06
[BOJ] 15683. 감시  (0) 2019.08.05

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

 

11559번: Puyo Puyo

현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.)

www.acmicpc.net

시뮬레이션 카테고리에 넣었지만 BFS도 이용하는 문제이다.

BFS는 상하좌우로 연결되어 있는 같은 색의 뿌요를 찾기 위해 사용한다.

 

 

먼저 연쇄가 몇 번 일어났는지를 알아내야 하는 문제이기 때문에 연쇄가 일어나지 않을 때까지 터뜨리기를 반복해야한다.

 

 

각 반복에서는 뿌요가 있는 모든 칸에 대해서 BFS탐색을 통해 상하좌우로 연결된 같은 색의 뿌요가 네 개 이상 있는지 체크해준다. 있다면 해당 칸의 뿌요들을 터뜨려주고(.으로 만들어 준다) 연쇄가 발생했다는 뜻으로 true를 리턴한다.

문제 조건에 따라 여러 그룹의 뿌요가 터졌더라도 연쇄는 한 번 일어난 걸로 간주한다.

예를 들어, 전체 칸을 탐색할 때 R이 4개 이상 모여있었고 다른 곳에서 G가 4개이상 모여있어서 두 그룹이 터졌다고 해도 같은 턴에 터지는 애들은 한번 일어난 걸로 count 해준다.

 

 

모든 뿌요에 대해서 탐색을 해줬는데 flag가 false라면 (한 번도 연쇄가 발생하지 않았다면) 반복문을 break 해주고 정답을 출력해주면 된다.

 

flag가 true라면(연쇄가 적어도 한 번 이상 발생했다면) 떠있는 뿌요들을 바닥에 내려주고 연쇄가 일어난 횟수(정답)를 증가시킨다.

 

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
 
char map[12][6];
int check[12][6];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int ans;
 
void move() {
    for (int j = 0; j < 6; j++) {
        for (int i = 11; i >= 0; i--) {
            if (map[i][j] != '.') continue;
 
            //빈 칸(.)을 찾았으므로 위에 떠있는 애를 찾는다.
            bool flag = false;
            for (int k = i - 1; k >= 0; k--) {
                
                //떠있는애 발견
                if (map[k][j] != '.') {
                    //내려준다.
                    map[i][j] = map[k][j];
                    map[k][j] = '.';
                    flag = true;
                    break;
                }
            }
 
            //위에 떠있는게 없으면 다음 열을 검사한다.
            if (!flag) {
                break;
            }
        }
    }
}
 
bool bfs(int x, int y) {
    queue<pair<int, int>> q;
    memset(check, false, sizeof(check));
    
    q.push(make_pair(x, y));
    check[x][y] = true;
    int cnt = 1;
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            
            //범위 체크
            if (nx < 0 || ny < 0 || nx >= 12 || ny >= 6) continue;
            //방문 체크
            if (check[nx][ny]) continue;
            //같은 색인지 체크
            if (map[nx][ny] != map[x][y]) continue;
 
            q.push(make_pair(nx, ny));
            check[nx][ny] = true;
            cnt++;
        }
    }
 
 
    //같은 색의 뿌요가 4개이상 존재하면 모두 터진다.
    if (cnt >= 4) {
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 6; j++) {
                if (check[i][j]) map[i][j] = '.';
            }
        }
        
 
        return true;
    }
    else return false;
}
 
void solve() {
    
    
    while (true) {
 
        bool flag = false;
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 6; j++) {
                if (map[i][j] == '.') continue; //빈칸
 
                //같은 색의 뿌요들이 4개이상 모여있어서 터지는지 검사
                if (bfs(i, j)) {
                    flag = true;
                }
 
            }
        }
 
        //더 이상 터질게 없다.
        if (!flag) break;
        else {
            //터졌으면 중력에 의해 뿌요들이 아래로 떨어진다.
            move();
 
            ans++;
        }
 
    }
 
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    string s;
    for (int i = 0; i < 12; i++) {
        cin >> s;
        for (int j = 0; j < 6; j++) {
            map[i][j] = s[j];
        }
    }
 
    solve();
 
 
    cout << ans << '\n';
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2573. 빙산  (0) 2019.08.13
[BOJ] 2234. 성곽  (0) 2019.08.13
[BOJ] 3190. 뱀  (0) 2019.08.06
[BOJ] 15683. 감시  (0) 2019.08.05
[BOJ] 14500. 테트로미노  (0) 2019.08.04

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

 

3190번: 뱀

문제  'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따

www.acmicpc.net

이 문제에서 어려운 점은 뱀이 자기 몸에 부딪혀서 게임이 끝날때를 처리해주는 부분인 것 같다.

이 부분은 몸길이와 칸에 머리가 있었던 시간을 저장한 배열을 이용하면 쉽게 구할 수 있다.

 

(현재 시간 - 몸길이)가 이동할 칸에 이전에 머리가 있었던 시간보다 작으면 몸에 부딪힌 것 이다

 

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
107
108
109
110
111
#include <iostream>
#include <vector>
using namespace std;
 
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
 
 
int n, k;
 
//사과의 좌표를 저장
bool apple[100][100];
 
//머리가 위치한 시간을 저장
int headtime[100][100];
 
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie();
 
    cin >> n >> k;
 
    //사과정보 저장
    int ax, ay;
    for (int i = 0; i < k; i++) {
        cin >> ax >> ay;
        apple[ax - 1][ay - 1] = true;
    }
 
    int l;
    cin >> l;
    int t;
    char c;
 
    //방향 회전 정보를 저장
    vector<pair<int, char>> vt;
    for (int i = 0; i < l; i++) {
        cin >> t;
        cin >> c;
        vt.push_back(make_pair(t,c));
    }
 
    int time = 0;
 
    //방향 회전정보를 이용하기 위한 인덱스
    int index = 0;
 
    //초기 방향
    int dir = 0;
 
    //초기 길이
    int len = 1;
 
    //초기 위치는 좌측 맨위쪽
    int x = 0;
    int y = 0;
    while (true) {
        //먼저 시간증가, 길이 증가, 머리 앞칸으로 이동
        time++;
        len += 1;
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        
        
        //벽에 부딪힘
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) break;
 
        //몸에 부딪힘 ((현재 시간 - 몸길이)가 이동할 칸에 머리가 있었던 시간보다 작으면 몸에 부딪힌 것 이다)
        if (headtime[nx][ny] != 0 && ((time - len) < headtime[nx][ny])) break;
 
        //이동한 칸에 현재 시간을 저장
        headtime[nx][ny] = time;
 
        //사과가 있는지 검사
        if (apple[nx][ny]) {
            apple[nx][ny] = false;
        }
        else {
            len -= 1;
        }
 
 
        //l번만큼 방향이동을 한다.
        if (index < l) {
            //현재시간이 방향을 회전해야하는 시간이다
            if (time == vt[index].first) {
                if (vt[index].second == 'D') {
                    dir = (dir + 1) % 4;
                }
                else if (vt[index].second == 'L') {
                    dir = (dir + 3) % 4;
                }
 
                //방향 전환했으면 index증가 (다음 방향 정보를 이용하기 위해)
                index++;
            }
        }
        
        //현재 좌표를 머리가 이동한 칸의 좌표로 변경
        x = nx;
        y = ny;
    }
 
 
 
    cout << time << '\n';
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2234. 성곽  (0) 2019.08.13
[BOJ] 11559. Puyo Puyo  (0) 2019.08.08
[BOJ] 15683. 감시  (0) 2019.08.05
[BOJ] 14500. 테트로미노  (0) 2019.08.04
[BOJ] 14499. 주사위 굴리기  (0) 2019.08.04

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

 

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할

www.acmicpc.net

CCTV구조체를 만들어서 CCTV의 좌표, 종류, 방향을 저장하게 했다.

방향은 나중에 모든 경우를 구해줄 때 저장한다.

모든 CCTV에 대해 방향을 정해줬으면 각 CCTV들의 감시 영역을 새로운 배열에 체크해주고

사각지대의 영역을 구해준다.

 

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <iostream>
#include <vector>
using namespace std;
 
int n, m;
int ans;
int map[8][8];
int dx[] = { 0,-1,0,1 };
int dy[] = { -1,0,1,0 };
 
struct CCTV {
    //감시카메라의 좌표
    int x;
    int y;
 
    //감시카메라 종류 번호
    int num;
 
    //감시할 방향 (나중에 정해준다)
    int dir;
    CCTV(int x, int y, int num) : x(x), y(y), num(num){}
};
 
vector<CCTV> vt;
 
 
//감시영역을 체크
void start(int x, int y, int dir, int newmap[8][8]) {
    while (true) {
        //dir 방향으로 계속 감시 영역을 표시한다.
        x += dx[dir];
        y += dy[dir];
 
        //범위 체크
        if (x < 0 || y < 0 || x >= n || y >= m) break;
        //벽이면 넘어갈 수 없다.
        if (map[x][y] == 6) break;
 
        //감시영역에 적당히 그냥 7넣어줬다.
        newmap[x][y] = 7;
    }
}
 
 
//모든 감시카메라들을 지정된 방향에 따라 감시영역을 표시한다.
int solve() {
    int newmap[8][8];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            newmap[i][j] = map[i][j];
        }
    }
 
    int vsize = vt.size();
    int x, y, num,dir;
    for (int i = 0; i < vsize; i++) {
        x = vt[i].x;
        y = vt[i].y;
        num = vt[i].num;
        dir = vt[i].dir;
 
        //종류에 따라서 감시영역을 표시한다.
        if (num == 1) {
            //한방향 감시
            start(x, y, dir, newmap);
        }
        else if (num == 2) {
            //반대방향이 두방향 감시
            start(x, y, dir, newmap);
            start(x, y, (dir+2)%4, newmap);
        }
        else if (num == 3) {
            //직각모양 두방향 감시
            start(x, y, dir, newmap);
            start(x, y, (dir+1)%4, newmap);
        }
        else if (num == 4) {
            //세방향 감시
            start(x, y, dir, newmap);
            start(x, y, (dir + 1) % 4, newmap);
            start(x, y, (dir + 2) % 4, newmap);
        }
        else if (num == 5) {
            //네 방향 모두 감시
            start(x, y, dir, newmap);
            start(x, y, (dir + 1) % 4, newmap);
            start(x, y, (dir + 2) % 4, newmap);
            start(x, y, (dir + 3) % 4, newmap);
        }
    }
 
 
    //처음에 사각지대였는데 감시영역을 표시한 이후에도 사각지대이면 cnt증가
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 0 && newmap[i][j] == 0) cnt++;
        }
    }
 
 
    //사각지대 수를 리턴
    return cnt;
}
 
 
//모든 감시카메라에 대해서 방향을 정해준다.
void select(int index) {
    if (index == vt.size()) {
        int tmp = solve();
 
        if (ans > tmp) ans = tmp;
        return;
    }
 
    for (int i = 0; i <= 3; i++) {
        vt[index].dir = i;
        select(index + 1);
    }
    
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie();
 
    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] >= 1 && map[i][j] <= 5) {
                vt.push_back(CCTV( i,j,map[i][j] ));
            }
        }
    }
 
 
    //정답이 될 수 있는 값보다 큰 값을 미리 저장
    ans = 65;
    select(0);
 
    cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 11559. Puyo Puyo  (0) 2019.08.08
[BOJ] 3190. 뱀  (0) 2019.08.06
[BOJ] 14500. 테트로미노  (0) 2019.08.04
[BOJ] 14499. 주사위 굴리기  (0) 2019.08.04
[BOJ] 14503. 로봇 청소기  (0) 2019.08.04

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

 

14500번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누

www.acmicpc.net

테트로미노는 (ㅏ,ㅓ,ㅗ,ㅜ)를 제외하고 시작점으로부터 인접한 칸으로 세 번 더 이동한 모양이다.

예를 들어 밑의 그림에서 대충 저 1을 시작점으로 잡았다고 쳤을 때 아무렇게나 인접한 칸으로 네 번 이동하면

테트로미노가 된다. 즉, 모든 경우를 해보면 (ㅏ,ㅓ,ㅗ,ㅜ)를 제외한 모든 테트로미노를 만들 수 있다.

 

           
  1 2      
    3      
    4      
           
           
           
           
  1 2      
    3 4    
           
           
           

 

모든 칸에서부터 시작하여 모든 종류의 테트로미노를 만들어주면 되는데

(ㅏ,ㅓ,ㅗ,ㅜ)는 밑에 코드처럼 따로 일일이 처리해주어야 한다.

ㅡ 에서 위아래로 튀어나온 부분(?)이랑 ㅣ 에서 좌우로 튀어나온 부분을 i, j로 놓고 그 나머지 부분을 추가적으로 더해줬다. 얘네도 범위를 벗어나지 않는다면 해당 네 칸을 더해준 다음에 최댓값과 각각 비교해주면 된다.

 

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
#include <iostream>
using namespace std;
 
 
int n, m;
int ans;
int map[500][500];
bool check[500][500];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
void solve(int x, int y, int sum, int cnt) {
    //테트로미노가 됐다!
    if (cnt == 4) {
        //최댓값을 비교하여 저장
        if (ans < sum) ans = sum;
        return;
    }
 
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
 
        //범위 체크
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
 
        //방문하지 않았다면 방문
        if (!check[nx][ny]) {
            check[nx][ny] = true;
            //sum에 현재 칸의 값을 더하여 넘겨준다. 현재칸을 선택했으므로 cnt도 증가
            solve(nx, ny, sum + map[nx][ny], cnt + 1);
            check[nx][ny] = false;
        }
    }
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
 
 
    //모든 칸에서 모든 테트로미노를 놓는 경우를 모두 해본다.
    int sum;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            check[i][j] = true;
            solve(i, j, map[i][j], 1);
            check[i][j] = false;
 
 
            //ㅏ
            if (i - 1 >= 0 && i + 1 < n && j + 1 < m) {
                sum = map[i][j];
                sum += map[i - 1][j + 1] + map[i][j + 1] + map[i + 1][j + 1];
                if (ans < sum) ans = sum;
            }
 
 
            //ㅗ
            if (i - 1 >= 0 && j - 1 >= 0 && j + 1 < m) {
                sum = map[i][j];
                sum += map[i - 1][j - 1] + map[i - 1][j] + map[i - 1][j + 1];
                if (ans < sum) ans = sum;
            }
 
 
            //ㅓ
            if (i - 1 >= 0 && i + 1 < n && j - 1 >= 0) {
                sum = map[i][j];
                sum += map[i - 1][j - 1] + map[i][j - 1] + map[i + 1][j - 1];
                if (ans < sum) ans = sum;
            }
 
 
            //ㅜ
            if (i + 1 < n && j - 1 >= 0 && j + 1 < m) {
                sum = map[i][j];
                sum += map[i + 1][j - 1] + map[i + 1][j] + map[i + 1][j + 1];
                if (ans < sum) ans = sum;
            }
 
        }
    }
 
    cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 3190. 뱀  (0) 2019.08.06
[BOJ] 15683. 감시  (0) 2019.08.05
[BOJ] 14499. 주사위 굴리기  (0) 2019.08.04
[BOJ] 14503. 로봇 청소기  (0) 2019.08.04
[BOJ] 14502. 연구소  (0) 2019.08.04

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

 

14499번: 주사위 굴리기

첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 주사위를 놓은 칸에 쓰여 있는 수는 항상 0이다. 지도의 각 칸에 쓰여 있는 수는 10을 넘지 않는 자연수 또는 0이다. 마

www.acmicpc.net

주사위

주사위 배열을 만들어놓고 위의 그림에 나와 있는 숫자를 배열의 인덱스로 사용하였다.

즉 dice[0] 이 윗면, dice[5]가 바닥면이다.

주사위를 굴릴 때마다 배열의 값을 주사위의 해당 면에 오는 숫자로 바꿔주면 된다.

쉽게 생각하면 주사위는 그대로 있고 주사위 위의 숫자가 굴리는 방향에 따라 움직인다고 생각하면 된다.

 

굴릴 방향에 따라서 어떻게 변하는지는 그냥 일일이 해주면 되는데

예를 들어 d가 1일 경우(동쪽으로 주사위를 굴리는 경우)

위의 그림에서 3번, 0번, 2번, 5번 면의 숫자가 바뀐다. 모두 동쪽으로 한 칸씩 움직이기 때문에

0번은 2번으로, 2번은 바닥면인 5번으로, 5번에 에 있던 숫자는 3번으로, 3번에 있던 숫자는 윗면인 0으로 올라오게 된다.

이런 식으로 네 방향에 대해서 하나하나 구해주면 된다.

 

주의할 점은 범위를 벗어나는 경우에 해당 명령을 무시해야 하므로 주사위가 이동하지 않도록 해야 한다.

밑의 코드에서는 nx, ny 변수를 새로 만들어서 범위를 검사해주고 범위를 벗어나지 않으면 x, y에 넣어줬다.


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
#include <iostream>
using namespace std;
 
int dx[] = { 0,0,0,-1,1 };
int dy[] = { 0,1,-1,0,0 };
 
int map[20][20];
int dice[6];
 
int n, m, x, y, k;
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
 
    cin >> n >> m >> x >> y >> k;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
 
    int dir;
    int nx, ny;
    while (k-- > 0) {
        cin >> dir;
 
        nx = x + dx[dir];
        ny = y + dy[dir];
 
        //범위를 벗어나면 명령을 무시
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
 
 
        if (dir == 1) {
            int tmp = dice[0];
            dice[0] = dice[3];
            dice[3] = dice[5];
            dice[5] = dice[2];
            dice[2] = tmp;
        }
        else if (dir == 2) {
            int tmp = dice[0];
            dice[0] = dice[2];
            dice[2] = dice[5];
            dice[5] = dice[3];
            dice[3] = tmp;
        }
        else if (dir == 3) {
            int tmp = dice[0];
            dice[0] = dice[4];
            dice[4] = dice[5];
            dice[5] = dice[1];
            dice[1] = tmp;
        }
        else if (dir == 4) {
            int tmp = dice[0];
            dice[0] = dice[1];
            dice[1] = dice[5];
            dice[5] = dice[4];
            dice[4] = tmp;
        }
 
 
        //지도의 칸이 0이면 주사위의 바닥면이 지도에 복사
        if (map[nx][ny] == 0) {
            map[nx][ny] = dice[5];
        }
        else {
            //그렇지 않다면 칸에 쓰여져 있는 수가 주사위 바닥면으로 복사 후에 0으로 변경
            dice[5] = map[nx][ny];
            map[nx][ny] = 0;
        }
 
 
        x = nx;
        y = ny;
 
 
        //윗면을 출력
        cout << dice[0] << '\n';
    }
 
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 15683. 감시  (0) 2019.08.05
[BOJ] 14500. 테트로미노  (0) 2019.08.04
[BOJ] 14503. 로봇 청소기  (0) 2019.08.04
[BOJ] 14502. 연구소  (0) 2019.08.04
[BOJ] 15685. 드래곤 커브  (0) 2019.08.04

+ Recent posts

티스토리툴바