반응형

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

 

16928번: 뱀과 사다리 게임

첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으

www.acmicpc.net

 

 

[ 문제풀이 ]

 

bfs를 활용하여 문제를 풀었습니다.

 

1. 각 칸을 자신으로 초기화합니다.

 

2. 사다리와 뱀을 입력받습니다.

 

3. bfs를 활용하여 100번 칸에 도착하면 답을 출력하고 종료합니다.

 

위의 3번 과정을 진행할 때 한 번의 과정 동안 6번의 반복을 하면서 방문 여부를 체크해주고, 방문하지 않았다면 queue에 넣어 다음 과정을 진행해 줍니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int arr[101];        //각 칸의 이동 위치
int visited[101];    //각 칸의 방문 여부
 
struct node {
    int cur;
    int cnt;
};
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= 100; i++) {    //각 칸의 이동 위치를 자신으로 초기화
        arr[i] = i;
    }
 
    for (int i = 0; i < N; i++) {    //사다리 입력
        int a, b;
        scanf("%d %d", &a, &b);
 
        arr[a] = b;
    }
 
    for (int i = 0; i < M; i++) {    //뱀 입력
        int a, b;
        scanf("%d %d", &a, &b);
 
        arr[a] = b;
    }
 
    queue<node> q;
    q.push({ 1, 0 });
 
    while (1)
    {
        int cur = q.front().cur;
        int cnt = q.front().cnt;
        q.pop();
 
        if (cur == 100) {    //100번 칸에 도착하면 cnt 출력 후 종료
            printf("%d", cnt);
            return 0;
        }
 
        if (visited[cur] == 1) continue;
        visited[cur] = 1;
 
        for (int i = 1; i <= 6; i++) {
            int next = arr[cur + i];    //이동할 칸
            if (visited[next] != 1) {
                q.push({ next, cnt + 1 });
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 3190번 - 뱀 (C++)  (0) 2022.08.15
[ 백준 ] 7576번 - 토마토 (C++)  (0) 2022.08.14
[ 백준 ] 9465번 - 스티커 (C++)  (0) 2022.08.12
[ 백준 ] 1932번 - 정수 삼각형 (C++)  (0) 2022.08.11
[ 백준 ] 17401번 - 일하는 세포 (C++)  (0) 2022.08.10
반응형

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

 

10026번: 적록색약

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

각각의 문자에 따라 구역을 0으로 바꿔주는 함수를 만들어서 적록색약이 아닌 사람이 볼 수 있는 구역의 수를 구해줍니다. 그리고 R과 G를 한 구역으로 찾는 함수를 하나 더 만들어주어서 적록색약인 사람이 볼 수 있는 구역의 수를 출력해줍니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
 
struct node {
    int y;
    int x;
};
 
void bfs(int y, int x, char ch, char temp[][101])
{
    queue<node> q;
    q.push({ y,x });
    temp[y][x] = 0;
 
    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                if (temp[yy][xx] == ch) {
                    temp[yy][xx] = 0;
                    q.push({ yy,xx });
                }
            }
        }
    }
}
 
void bfsRG(int y, int x, char temp[][101])
{
    queue<node> q;
    q.push({ y,x });
    temp[y][x] = 0;
 
    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                if (temp[yy][xx] == 'R' || temp[yy][xx] == 'G') {
                    temp[yy][xx] = 0;
                    q.push({ yy,xx });
                }
            }
        }
    }
}
 
int main()
{
    scanf("%d", &N);
 
    char arr[101][101];
    char temp[101][101];
 
    for (int i = 0; i < N; i++) {
        scanf("%s", arr[i]);
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            temp[i][j] = arr[i][j];
        }
    }
 
    int cnt = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (temp[i][j] == 'R') {
                cnt++;
                bfs(i, j, 'R', temp);
            }
            else if (temp[i][j] == 'G') {
                cnt++;
                bfs(i, j, 'G', temp);
            }
            else if (temp[i][j] == 'B') {
                cnt++;
                bfs(i, j, 'B', temp);
            }
        }
    }
 
    printf("%d ", cnt);
 
    cnt = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == 'R' || arr[i][j] == 'G') {
                cnt++;
                bfsRG(i, j, arr);
            }
            else if (arr[i][j] == 'B') {
                cnt++;
                bfs(i, j, 'B', arr);
            }
        }
    }
 
    printf("%d", cnt);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 7578번 - 공장 (C++)  (0) 2022.08.07
[ 백준 ] 16287번 - Parcel (C++)  (0) 2022.08.06
[ 백준 ] 11438번 - LCA 2 (C++)  (0) 2022.08.04
[ 백준 ] 1725번 - 히스토그램 (C++)  (0) 2022.08.03
[ 백준 ] 6549번 - 히스토그램에서 가장 큰 직사각형 (C++)  (0) 2022.08.02
반응형

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

 

11725번: 트리의 부모 찾기

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

먼저 vector를 이용하여 그래프 입력을 받고, 입력받은 그래프를 바탕으로 DFS를 돌려 문제를 풀 수 있습니다. 한번 방문한 노드는 다시 방문할 필요가 없으므로 visited배열을 통해 방문 체크를 해주시면 됩니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N;
vector<int> list[100001];
int visited[100001];
int parent[100001];
 
void dfs(int node)
{
    if (visited[node] == 1) return;
    visited[node] = 1;
 
    for (auto next : list[node]) {
        if (visited[next] != 1) {
            parent[next] = node;
            dfs(next);
        }
    }
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        list[a].push_back(b);
        list[b].push_back(a);
    }
 
    dfs(1);
 
    for (int i = 2; i <= N; i++) {
        printf("%d\n", parent[i]);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 6549번 - 히스토그램에서 가장 큰 직사각형 (C++)  (0) 2022.08.02
[ 백준 ] 1629번 - 곱셈 (C++)  (0) 2022.08.01
[ 백준 ] 11444번 - 피보나치 수 6 (C++)  (0) 2022.07.30
[ 백준 ] 2243번 - 사탕상자 (C++)  (0) 2022.07.29
[ 백준 ] 5719번 - 거의 최단 경로 (C++)  (0) 2022.07.27
반응형

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

 

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크

www.acmicpc.net

 

 

[ 문제풀이 ]

 

재귀 함수를 통해서 벽을 세우고 bfs를 이용하여 바이러스를 퍼뜨린 후 안전 영역의 크기를 구해주면 되는 문제입니다.

 

맵의 최대 크기는 8 X 8 이므로 벽을 세우는데 최대 O(64*63*62)의 시간이 걸리므로 모든 경우의 수를 다 탐색하더라도 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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int arr[8][8];
int dy[4] = { 0,0,-1,1 };
int dx[4] = { -1,1,0,0 };
int ans;
 
struct pos {
    int y;
    int x;
};
 
int bfs(int map[][8])        //바이러스를 퍼트린 후 안전 영역의 크기를 출력
{
    queue<pos>q;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 2) {
                q.push({ i,j });
            }
        }
    }
 
    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (map[yy][xx] == 0) {
                    map[yy][xx] = 2;
                    q.push({ yy,xx });
                }
            }
        }
    }
 
    int cnt = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 0) {
                cnt++;
            }
        }
    }
 
    return cnt;
}
 
void dfs(int level, int num)        //벽을 세우기 위한 재귀함수
{
    if (level == 3) {            //벽이 3개라면
        int temp[8][8] = { 0 };
        for (int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                temp[i][j] = arr[i][j];
            }
        }
 
        int cnt = bfs(temp);
 
        if (ans < cnt) {
            ans = cnt;
        }
 
        return;
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (N * i + j > num) {        //이전에 벽을 세운 곳 다음부터 탐색
                if (arr[i][j] == 0) {
                    arr[i][j] = 1;
                    dfs(level + 1, i * N + j);
                    arr[i][j] = 0;
                }
            }
        }
    }
}
 
int main()
{
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }
 
    dfs(0, -1);
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 2096번 - 내려가기 (C++)  (0) 2022.07.08
[ 백준 ] 5639번 - 이진 검색 트리 (C++)  (0) 2022.07.07
[ 백준 ] 2357번 - 최솟값과 최댓값 (C++)  (0) 2022.07.05
[ 백준 ] 2042번 - 구간 합 구하기 (C++)  (0) 2022.07.04
[ 백준 ] 1019번 - 책 페이지 (C++)  (0) 2022.07.03
반응형

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

 

9328번: 열쇠

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가

www.acmicpc.net

 

 

[ 문제풀이 ]

 

queue 두 개를 활용해서 bfs를 돌리면 쉽게 구할 수 있는 문제였습니다.

 

먼저 맵을 입력받을 때 탐색이 좀 더 쉽도록 배열의 1번 인덱스부터 w, h까지 입력을 받습니다. 그 이유는 가장 바깥쪽의 테두리는 자유롭게 다닐 수 있게 하여서 맵에 들어갈 수 있는 입구가 있다면 들어갈 수 있도록 설정하면 0, 0에서 시작하면 되기 때문입니다.

 

 

문을 만나면 키를 가지고 있는지 확인한 다음에 키가 있다면 그냥 열고 지나가고, 없다면 다음에 열쇠가 생겼을 때 열 수 있도록 door이라는 queue에 문의 좌표를 저장해 두었습니다.

 

그리고 키를 만나면 이 키로 열 수 있는 문이 있는지 체크하고 있다면 그 좌표를 q에 집어넣고, 없다면 그냥 지나가는 방법으로 문제를 풀었습니다.

 

[ 소스 코드 ]

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
#include <iostream>
#include <queue>
#include <string>
#include <cstring>
 
using namespace std;
 
char arr[111][111];            //지도
int visited[111][111];        //방문 여부 체크
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
struct pos {
    int y;
    int x;
};
 
int main()
{
    int T;
    cin >> T;
 
    for (int t = 0; t < T; t++) {
        int h, w;
        int key[26] = { 0 };        //몇번 키를 가지고 있는지 체크할 배열
        memset(visited, 0, sizeof(visited));
        memset(arr, 0, sizeof(arr));
        queue<pos> q;
        queue<pos> door[26];        //열쇠가 없는 문에 닿았을 때 좌표 저장
        int cnt = 0;
        cin >> h>> w;
 
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                cin >> arr[i][j];
            }
        }
 
        string str = "";
        cin >> str;
        if (str != "0") {
            for (int i = 0; i < str.size(); i++) {
                key[str[i] - 'a']++;
            }
        }
 
        q.push({ 0,0 });
        visited[0][0] = 1;
 
        while (!q.empty())
        {
            int y = q.front().y;
            int x = q.front().x;
            q.pop();
 
            for (int i = 0; i < 4; i++) {
                int yy = y + dy[i];
                int xx = x + dx[i];
                if (yy >= 0 && yy <= h + 1 && xx >= 0 && xx <= w + 1) {
                    if (visited[yy][xx] == 1 || arr[yy][xx] == '*') continue;
                    visited[yy][xx] = 1;
                    
                    if (arr[yy][xx] >= 'A' && arr[yy][xx] <= 'Z') {
                        if (key[arr[yy][xx] - 'A'] == 1) {    //열쇠가 있다면 통과
                            q.push({ yy,xx });
                        }
                        else {
                            door[arr[yy][xx] - 'A'].push({ yy,xx });    //없다면 좌표를 저장
                        }
                    }
                    else if (arr[yy][xx] >= 'a' && arr[yy][xx] <= 'z') {
                        key[arr[yy][xx] - 'a'] = 1;        //키를 가지고 있다고 체크
                        while (!door[arr[yy][xx] - 'a'].empty()) {    //키로 열 수 있는 문 좌표 q에 push
                            int curKey = arr[yy][xx] - 'a';
                            int curY = door[curKey].front().y;
                            int curX = door[curKey].front().x;
                            door[curKey].pop();
                            q.push({ curY,curX });
                        }
                        q.push({ yy,xx });
                    }
                    else if (arr[yy][xx] == '$') {        //문서면 cnt++
                        cnt++;
                        q.push({ yy,xx });
                    }
                    else {
                        q.push({ yy,xx });
                    }
                }
            }
        }
 
        cout << cnt << endl;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 2098번 - 외판원 순회 (C++)  (0) 2022.06.22
[ 백준 ] 14003번 - 가장 긴 증가하는 부분 수열 5 (C++)  (0) 2022.06.21
[ 백준 ] 1167번 - 트리의 지름 (C++)  (0) 2022.06.19
[ 백준 ] 17404번 - RGB거리 2 (C++)  (0) 2022.06.18
[ 백준 ] 7662번 - 이중 우선순위 큐 (C++)  (0) 2022.06.17
반응형

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

 

13549번: 숨바꼭질 3

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

 

 

[ 문제풀이 ]

 

dp를 이용해서 풀 수 있는 문제였습니다.

 

이동할 수 있는 방법은 -1, 1, *2 총 3개였습니다. 이때 *2로 이동할 때는 시간이 0의 시간이 걸리고, 나머지 이동 중에는 1의 시간이 걸립니다.

 

그렇다면 N보다 작거나 같은 칸으로 이동할 때는 무조건 한 칸에 1씩 걸리므로 dp [ i ] = N - i 가 됩니다.

 

나머지 경우에는 i가 짝수일 때 dp[ i + 1 ] + 1, dp [ i - 1 ] + 1, dp [ i / 2 ] 중 가장 작은 값을 선택하면 되고, 홀수일 때는 dp [ i + 1 ] + 1, dp [ i - 1 ] + 1 중 가장 작은 값을 선택하면 됩니다.

 

또한 순간이동 시 이동시간이 2이므로 각 노드에 도착했을 때 *2로 이동할 수 있는 모든 칸에 대하여 dp [ cur ] < dp [ next ] 일 경우에 dp [ next ] = dp [ cur ]로 바꿔주면 됩니다.

 

마지막으로 dp[ K ]를 출력합니다.

 

[ 소스 코드 ]

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
#include <iostream>
 
using namespace std;
 
int N, K;
int dp[200001];
 
void tel(int num)
{
    int cur = num;
    while (1) {
        num *= 2;
        if (num > 200001) {
            break;
        }
        if (dp[num] > dp[cur]) {
            dp[num] = dp[cur];
        }
    }
}
 
int main()
{
    cin >> N >> K;
 
    for (int i = 0; i < 200001; i++) {
        dp[i] = 987654321;
    }
 
    for (int i = 0; i < 200001; i++) {
        if (i <= N) {
            dp[i] = N - i;
        }
        else {
            if (i % 2 == 0) {
                dp[i] = min(min(dp[i - 1] + 1, dp[i + 1] + 1), dp[i / 2]);
            }
            else {
                dp[i] = min(dp[i - 1] + 1, dp[i + 1] + 1);
            }
        }
        if (i > 0) {
            tel(i);
        }
    }
 
    cout << dp[K];
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 7662번 - 이중 우선순위 큐 (C++)  (0) 2022.06.17
[ 백준 ] 1967번 - 트리의 지름 (C++)  (0) 2022.06.16
[ 백준 ] 9935번 - 문자열 폭발 (C++)  (0) 2022.06.14
[ 백준 ] 2638번 - 치즈 (C++)  (0) 2022.06.13
[ 백준 ] 13460번 - 구슬 탈출 2 (C++)  (0) 2022.06.12
반응형

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

 

2638번: 치즈

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로

www.acmicpc.net

 

 

[ 문제풀이 ]

 

BFS를 이용한 구현 문제였습니다.

 

주어진 모눈종이의 테두리는 치즈가 없다고 하였으므로 0, 0부터 BFS를 돌려 치즈로 둘러싸여 있지 않은 공간들을 2로 초기화시켜주고 치즈들 중 2칸 이상 2에 닿아있는 치즈는 녹이면서 진행하였습니다.

 

그리고 다시 0, 0부터 BFS를 돌려 빈 공간들을 2로 초기화시켜주면서 위의 과정을 반복하고, 치즈가 다 사라지면 BFS를 돌린 횟수를 출력하였습니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<queue>
#include<cstring>
 
using namespace std;
 
int N, M;
int map[100][100];
int visited[100][100];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
struct pos {
    int y;
    int x;
};
 
void bfs(int y, int x)        //치즈에 둘러쌓여 있지 않은 공간을 2로 초기화
{
    queue<pos> q;
    memset(visited, 0, sizeof(visited));
    q.push({ y,x });
    visited[y][x] = 1;
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        map[curY][curX] = 2;
 
        for (int i = 0; i < 4; i++) {
            int yy = curY + dy[i];
            int xx = curX + dx[i];
            if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (map[yy][xx] != 1 && visited[yy][xx] != 1) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                }
            }
        }
    }
}
 
int check()        //치즈가 다 녹았는지 체크하는 함수
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 1) {
                return 0;
            }
        }
    }
 
    return 1;
}
 
int Cnt(int y, int x)    //실내 온도에 노출 된 횟수를 출력
{
    int cnt = 0;
    for (int i = 0; i < 4; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
        if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
            if (map[yy][xx] == 2) {
                cnt++;
            }
        }
    }
 
    return cnt;
}
 
int main()
{
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }
 
    int cnt = 0;
 
    while (!check())        //치즈가 다 녹을 때까지
    {
        bfs(0, 0);        //0, 0부터 2로 빈 공간 2로 초기화
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 1) {    //2칸 이상 닿아있다면 녹임
                    if (Cnt(i, j) >= 2) {
                        map[i][j] = 0;
                    }
                }
            }
        }
 
        cnt++;        //횟수 추가
    }
 
    cout << cnt;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 13549번 - 숨바꼭질 3 (C++)  (0) 2022.06.15
[ 백준 ] 9935번 - 문자열 폭발 (C++)  (0) 2022.06.14
[ 백준 ] 13460번 - 구슬 탈출 2 (C++)  (0) 2022.06.12
[ 백준 ] 11404번 - 플로이드 (C++)  (0) 2022.06.11
[ 백준 ] 1865번 - 웜홀 (C++)  (0) 2022.06.10
반응형

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

 

13460번: 구슬 탈출 2

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'

www.acmicpc.net

 

 

[ 문제풀이 ]

 

BFS를 이용한 구현 문제였습니다.

 

먼저 move 함수를 통해서 공들을 옮겨줍니다. 공을 움직이고 나서 각 공의 좌표를 visited 배열에 저장해서 이전에 똑같은 상황이 있었다면 queue에 넣지 않는 식으로 구현하였습니다.

 

또한, 공을 움직인 횟수가 10회를 초과했다면 continue 하였고, 둘 다 구멍에 들어갔다면 마찬가지로 continue 해주었습니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
struct state {
    int Ry;
    int Rx;
    int By;
    int Bx;
    int cnt;
};
 
int N, M;
char map[10][10];
char temp[10][10];
int visited[10][10][10][10];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int Ry;
int Rx;
int By;
int Bx;
int ans;
 
void move(int num)                    //구슬을 움직이기 위한 move 함수
{
    for (int i = 1; i < 10; i++) {    //빨간 구슬 옮기기
        int yy = Ry + dy[num] * i;
        int xx = Rx + dx[num] * i;
        if (temp[yy][xx] == 'O') {
            temp[Ry][Rx] = '.';
            Ry = 0;
            Rx = 0;
            break;
        }
        else if (temp[yy][xx] != '.') {
            temp[Ry][Rx] = '.';
            Ry = Ry + dy[num] * (i - 1);
            Rx = Rx + dx[num] * (i - 1);
            temp[Ry][Rx] = 'R';
            break;
        }
    }
 
    for (int i = 1; i < 10; i++) {    //파란 구슬 옮기기
        int yy = By + dy[num] * i;
        int xx = Bx + dx[num] * i;
        if (temp[yy][xx] == 'O') {
            temp[By][Bx] = '.';
            By = 0;
            Bx = 0;
            break;
        }
        else if (temp[yy][xx] != '.') {
            temp[By][Bx] = '.';
            By = By + dy[num] * (i - 1);
            Bx = Bx + dx[num] * (i - 1);
            temp[By][Bx] = 'B';
            break;
        }
    }
}
 
int main()
{
    cin >> N >> M;
 
    queue<state> q;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'R') {
                map[i][j] = '.';
                Ry = i;
                Rx = j;
            }
            else if (map[i][j] == 'B') {
                map[i][j] = '.';
                By = i;
                Bx = j;
            }
        }
    }
 
    q.push({ Ry,Rx,By,Bx,0 });
    visited[Ry][Rx][By][Bx] = 1;
 
    while (!q.empty())
    {
        int curRy = q.front().Ry;
        int curRx = q.front().Rx;
        int curBy = q.front().By;
        int curBx = q.front().Bx;
        int cnt = q.front().cnt;
        q.pop();
 
        if (curRy == 0 && curBy != 0) {        //빨간 구슬만 들어갔을 때 cnt출력
            cout << cnt;
            return 0;
        }
        else if (curRy == 0 && curBy == 0 || cnt >= 10) {
            continue;                        //둘 다 들어갔거나 10번 초과이면 continue
        }
 
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < N; j++) {    //map배열을 temp배열에 복사
                for (int k = 0; k < M; k++) {
                    temp[j][k] = map[j][k];
                }
            }
            Ry = curRy;
            Rx = curRx;
            By = curBy;
            Bx = curBx;
            temp[Ry][Rx] = 'R';                //구슬을 배치
            temp[By][Bx] = 'B';
            for (int j = 0; j < 2; j++) {    //완벽하게 움직이기 위해서 두번 움직임
                move(i);
            }
 
            if (visited[Ry][Rx][By][Bx] != 1) {//이전에 같은 상태가 있었다면 q에 넣지 않기
                visited[Ry][Rx][By][Bx] = 1;
                q.push({ Ry,Rx,By,Bx,cnt + 1 });
            }
        }
    }
 
    cout << -1;        //10번 초과했거나 항상 두 구슬이 다 들어가는 경우
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 9935번 - 문자열 폭발 (C++)  (0) 2022.06.14
[ 백준 ] 2638번 - 치즈 (C++)  (0) 2022.06.13
[ 백준 ] 11404번 - 플로이드 (C++)  (0) 2022.06.11
[ 백준 ] 1865번 - 웜홀 (C++)  (0) 2022.06.10
[ 백준 ] 1238번 - 파티 (C++)  (0) 2022.06.09

+ Recent posts

티스토리툴바