반응형

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

 

17141번: 연구소 2

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 연구소를 입력받을 때 벽을 -1로 바꾸고 바이러스의 위치를 vector에 따로 저장한 후 0으로 바꿉니다.

 

2. 재귀함수를 통해 바이러스를 놓을 위치를 정하고 바이러스를 다 놓은 후 bfs를 통해 바이러스가 모두 퍼질 때까지 걸린 시간을 ans에 저장합니다.

 

3. ans의 값 중 가장 작은 값을 출력합니다.

 

4. 만약 어떠한 경우에도 바이러스를 모두 퍼뜨릴 수 없다면 -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
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
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int N, M;
int arr[50][50];
vector<pair<int, int>> virus;
int pos[10];
int ans = 987654321;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
int bfs()
{
    queue<pair<int, int>>q;
    int ret = 0;
    int cnt = 0;
 
    int temp[50][50] = { 0 };
    int visited[50][50] = { 0 };
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            temp[i][j] = arr[i][j];
        }
    }
 
    for (int i = 0; i < M; i++) {
        int y = virus[pos[i]].first;
        int x = virus[pos[i]].second;
        q.push({ y,x });
        visited[y][x] = 1;
    }
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        ret = max(ret, temp[y][x]);
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                if (visited[yy][xx] != 1 && temp[yy][xx] != -1) {
                    visited[yy][xx] = 1;
                    temp[yy][xx] = temp[y][x] + 1;
                    q.push({ yy,xx });
                }
            }
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (temp[i][j] == 0) cnt++;
        }
    }
 
    if (cnt > M) {
        ret = 987654321;
    }
 
    return ret;
}
 
void dfs(int level, int n)
{
    if (level == M) {
        ans = min(ans, bfs());
        return;
    }
 
    for (int i = n; i < virus.size(); i++) {
        pos[level] = i;
        dfs(level + 1, i + 1);
    }
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] == 2) {
                virus.emplace_back(i, j);
                arr[i][j] = 0;
            }
            else if (arr[i][j] == 1) {
                arr[i][j] = -1;
            }
        }
    }
 
    dfs(0, 0);
 
    if (ans == 987654321) {
        printf("-1");
    }
    else {
        printf("%d", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14226번 - 이모티콘 (C++)  (0) 2023.01.08
[ 백준 ] 2470번 - 두 용액 (C++)  (0) 2023.01.07
[ 백준 ] 1275번 - 커피숍2 (C++)  (0) 2023.01.05
[ 백준 ] 10868번 - 최솟값 (C++)  (0) 2023.01.04
[ 백준 ] 3745번 - 오름 (C++)  (0) 2023.01.03
반응형

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

 

17244번: 아맞다우산

경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 입력을 받고, X를 만날 때마다 ea변수를 1씩 늘려주고, X를 ea의 값으로 바꿔줍니다.

 

2. visited [ ea ][ y ][ x ] 배열을 만들어 주운 물건을 비트마스킹을 통해 체크하고, 방문 여부를 체크합니다. 이때, ea의 최댓값은 $2^{5}$(=32)입니다.

 

3. 물건을 주울 때마다 stf 변수에 현재 물건의 번호를 통해 추가해줍니다.

 

4. 모든 물건을 다 줍고, 도착점에 도착하면 cnt를 출력합니다.

 

[ 소스코드 ]

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>
 
using namespace std;
 
int N, M;
char arr[51][51];
int Sy, Sx;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int visited[32][51][51];
 
struct node {
    int y;
    int x;
    int cnt;
    int stf;
};
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < M; i++) {
        scanf("%s", &arr[i]);
    }
 
    int ea = 0;
 
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == 'S') {
                Sy = i;
                Sx = j;
            }
            else if (arr[i][j] == 'X') {
                arr[i][j] = '0' + ea;
                ea++;
            }
        }
    }
 
    queue<node> q;
 
    q.push({ Sy,Sx,0,0 });
    visited[0][Sy][Sx] = 1;
 
    while (!q.empty()) {
        const int y = q.front().y;
        const int x = q.front().x;
        const int cnt = q.front().cnt;
        const int stf = q.front().stf;
        q.pop();
 
        if (arr[y][x] == 'E') {
            if (stf == (1 << ea) - 1) {
                printf("%d", cnt);
            }
        }
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < M && xx >= 0 && xx < N) {
                if (arr[yy][xx] >='0' && arr[yy][xx] <'5') {
                    const int temp = stf | (1 << (arr[yy][xx] - '0'));
                    if (visited[temp][yy][xx] != 1) {
                        visited[temp][yy][xx] = 1;
                        q.push({ yy,xx,cnt + 1,temp });
                    }
                }
                else if (arr[yy][xx] != '#') {
                    if (visited[stf][yy][xx] != 1) {
                        visited[stf][yy][xx] = 1;
                        q.push({ yy,xx,cnt + 1,stf });
                    }
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14438번 - 수열과 쿼리 17 (C++)  (0) 2023.01.02
[ 백준 ] 12837번 - 가계부 (Hard) (C++)  (0) 2023.01.01
[ 백준 ] 17497번 - 계산 (C++)  (0) 2022.12.30
[ 백준 ] 2268번 - 수들의 합 7 (C++)  (0) 2022.12.29
[ 백준 ] 1194번 - 달이 차오른다, 가자. (C++)  (0) 2022.12.28
반응형

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

 

1194번: 달이 차오른다, 가자.

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고,

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 민식이의 이동을 기록할 visited [ key ][ y ][ x ] 배열을 만듭니다. 여기서 key의 최댓값은 a~f까지 총 6개이므로 $2^{6}$(=128)입니다.

 

2. bfs를 통해 이동을 하다가 a~f사이 알파벳을 만나면 현재 key에 1 << arr [ y ][ x ] - 'a'의 값을 추가해 줍니다.

 

3. 이동 중 A~F사이 알파벳을 만나면 현재 key에 1 << arr [ y ][ x ] - 'A'의 값이 존재하면 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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
char arr[51][51];
int visited[130][50][50];
int Sy, Sx;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
struct node {
    int y;
    int x;
    int key;
    int cnt;
};
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++) {
        scanf("%s", &arr[i]);
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == '0') {
                arr[i][j] = '.';
                Sy = i;
                Sx = j;
            }
        }
    }
 
    queue<node> q;
    q.push({ Sy,Sx,0,0 });
    visited[0][Sy][Sx] = 1;
 
    while (!q.empty()) {
        const int y = q.front().y;
        const int x = q.front().x;
        const int key = q.front().key;
        const int cnt = q.front().cnt;
        q.pop();
 
        if (arr[y][x] == '1') {
            printf("%d", cnt);
            return 0;
        }
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (arr[yy][xx] == '.' || arr[yy][xx] == '1') {
                    if (visited[key][yy][xx] != 1) {
                        visited[key][yy][xx] = 1;
                        q.push({ yy,xx,key,cnt + 1 });
                    }
                }
                else if (arr[yy][xx] >= 'a' && arr[yy][xx] <= 'f') {
                    int newKey = key | (1 << arr[yy][xx] - 'a');
                    if (visited[newKey][yy][xx] != 1) {
                        visited[newKey][yy][xx] = 1;
                        q.push({ yy,xx,newKey,cnt + 1 });
                    }
                }
                else if (arr[yy][xx] >= 'A' && arr[yy][xx] <= 'F') {
                    if (1 << (arr[yy][xx] - 'A') & key) {
                        if (visited[key][yy][xx] != 1) {
                            visited[key][yy][xx] = 1;
                            q.push({ yy,xx,key,cnt + 1 });
                        }
                    }
                }
            }
        }
    }
 
    printf("-1");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17497번 - 계산 (C++)  (0) 2022.12.30
[ 백준 ] 2268번 - 수들의 합 7 (C++)  (0) 2022.12.29
[ 백준 ] 2589번 - 보물섬 (C++)  (0) 2022.12.27
[ 백준 ] 23793번 - 두 단계 최단 경로 1 (C++)  (0) 2022.12.26
[ 백준 ] 1759번 - 암호 만들기 (C++)  (0) 2022.12.25
반응형

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

 

2589번: 보물섬

첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 좌표에서 bfs를 통해 가장 먼 땅까지의 거리를 return 합니다.

 

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

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

[ 백준 ] 2268번 - 수들의 합 7 (C++)  (0) 2022.12.29
[ 백준 ] 1194번 - 달이 차오른다, 가자. (C++)  (0) 2022.12.28
[ 백준 ] 23793번 - 두 단계 최단 경로 1 (C++)  (0) 2022.12.26
[ 백준 ] 1759번 - 암호 만들기 (C++)  (0) 2022.12.25
[ 백준 ] 19538번 - 루머 (C++)  (0) 2022.12.24
반응형

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

 

19538번: 루머

예제 1 0분 : 최초 유포자($1$, $6$번 사람)가 루머를 생성한다. 1분 : $1$번 사람은 $2$, $3$번 사람에게 루머를 퍼뜨린다. $2$번 사람은 주변인 $2$명 중 $1$명이 루머를 믿고 있어 루머를 믿게 된다. $3$

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. vector list를 만들어 그래프를 저장합니다.

 

2. visited 배열과 cnt 배열을 만들어 i번 사람이 루머를 믿는지와 i번 사람의 주변에 루머를 믿는 사람의 수를 각각 저장합니다.

 

3. bfs를 통해 i번 사람이 루머를 믿게 될 때 주변 사람들의 cnt 배열 값을 1씩 늘려줍니다.

 

4. list[ next ].size() / 2 보다 cnt [ next ]의 값이 크거나 같으면 queue에 넣고 ans [ next ]에 현재 시간에 1을 더한 값을 저장하고, 방문 처리를 해줍니다.

 

5. for문으로 모든 노드를 돌면서 ans 값을 출력합니다.

 

[ 소스코드 ]

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<vector>
#include<queue>
#include<cstring>
 
using namespace std;
 
int N, M;
vector<int> list[200001];
int visited[200001];
int ans[200001];
int cnt[200001];
 
int main()
{
    queue<pair<int,int>> q;
    scanf("%d", &N);
 
    memset(ans, -1, 4 * (N + 1));
 
    int n;
 
    for (int i = 1; i <= N; i++) {
        while (1) {
            scanf("%d", &n);
            if (n == 0) break;
            list[i].push_back(n);
        }
    }
 
    scanf("%d", &M);
 
    for (int i = 0; i < M; i++) {
        scanf("%d", &n);
        q.push({ n, 0 });
        ans[n] = 0;
        visited[n] = 1;
    }
 
    while (!q.empty()) {
        const int cur = q.front().first;
        const int min = q.front().second;
        q.pop();
 
        for (auto next : list[cur]) {
            if (visited[next] != 1) {
                cnt[next]++;
 
                if (cnt[next] >= (float)list[next].size() / 2.0f) {
                    visited[next] = 1;
                    ans[next] = min + 1;
                    q.push({ next, min + 1 });
                }
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        printf("%d ", ans[i]);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 23793번 - 두 단계 최단 경로 1 (C++)  (0) 2022.12.26
[ 백준 ] 1759번 - 암호 만들기 (C++)  (0) 2022.12.25
[ 백준 ] 1922번 - 네트워크 연결 (C++)  (0) 2022.12.23
[ 백준 ] 14395번 - 4연산 (C++)  (0) 2022.12.22
[ 백준 ] 12738번 - 가장 긴 증가하는 부분 수열 3 (C++)  (0) 2022.12.21
반응형

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

 

14395번: 4연산

첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다.  연산의 아

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. unordered_map을 활용하여 s의 방문 여부를 체크합니다.

 

2. bfs를 돌면서 우선순위를 '*', '+', '-', '/' 순으로 queue에 push 합니다.

 

3. s와 t가 같아지면 지금까지 수행된 연산을 출력합니다.

 

4. s가 t와 같아질 수 없다면 -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
#include<iostream>
#include<queue>
#include<string>
#include<unordered_map>
#define ll long long
 
using namespace std;
 
int main()
{
    ll s, t;
    unordered_map<ll, int> m;
 
    scanf("%lld %lld", &s, &t);
 
    if (s == t) {
        printf("0");
        return 0;
    }
 
    queue<pair<ll, string>> q;
 
    string str;
 
    q.push({ s,str });
 
    while (!q.empty()) {
        const ll cur = q.front().first;
        const string str = q.front().second;
        q.pop();
 
        if (m[cur] != 0) continue;
        m[cur] = 1;
 
        if (cur == t) {
            cout << str;
            return 0;
        }
 
        if (cur * cur <= t) {
            if (m[cur * cur] != 1) {
                q.push({ cur * cur,str + '*' });
            }
        }
 
        if (cur * 2 <= t) {
            if (m[cur * 2] != 1) {
                q.push({ cur * 2,str + '+' });
            }
        }
 
        if (m[0] != 1) {
            q.push({ 0, str + '-' });
        }
 
        if (cur != 0) {
            if (m[1] != 1) {
                q.push({ 1,str + '/' });
            }
        }
    }
 
    printf("-1");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 19538번 - 루머 (C++)  (0) 2022.12.24
[ 백준 ] 1922번 - 네트워크 연결 (C++)  (0) 2022.12.23
[ 백준 ] 12738번 - 가장 긴 증가하는 부분 수열 3 (C++)  (0) 2022.12.21
[ 백준 ] 1818번 - 책정리 (C++)  (0) 2022.12.20
[ 백준 ] 22255번 - 호석사우루스 (C++)  (0) 2022.12.19
반응형

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

 

6593번: 상범 빌딩

당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 빌딩의 상태를 입력받고, 시작점의 좌표를 저장합니다.

 

2. bfs를 이용하여 S에서 시작해서 E에 도착할 때까지의 시간을 출력합니다.

 

3. 만약 도착할 수 없다면 Trapped!를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int L, R, C;
char arr[31][31][31];
int dl[6] = { 0,0,0,0,-1,1 };
int dr[6] = { -1,1,0,0,0,0 };
int dc[6] = { 0,0,-1,1,0,0 };
int Sl, Sr, Sc, El, Er, Ec;
 
struct node {
    int l;
    int r;
    int c;
    int cnt;
};
 
int main()
{
    while (1) {
        scanf("%d %d %d", &L,&R,&C);
 
        if (L == 0 && R == 0 && C == 0) {
            return 0;
        }
 
        for (int i = 0; i < L; i++) {
            for (int j = 0; j < R; j++) {
                scanf("%s", arr[i][j]);
            }
        }
 
        for (int i = 0; i < L; i++) {
            for (int j = 0; j < R; j++) {
                for (int k = 0; k < C; k++) {
                    if (arr[i][j][k] == 'S') {
                        Sl = i;
                        Sr = j;
                        Sc = k;
                    }
                }
            }
        }
 
        queue<node> q;
        int visited[31][31][31] = { 0 };
 
        q.push({ Sl,Sr,Sc,0 });
        visited[Sl][Sr][Sc] = 1;
 
        int ans = 0;
 
        while (!q.empty()) {
            const int l = q.front().l;
            const int r = q.front().r;
            const int c = q.front().c;
            const int cnt = q.front().cnt;
            q.pop();
 
            if (arr[l][r][c] == 'E') {
                ans = cnt;
                break;
            }
 
            for (int i = 0; i < 6; i++) {
                const int ll = l + dl[i];
                const int rr = r + dr[i];
                const int cc = c + dc[i];
 
                if (ll >= 0 && ll < L && rr >= 0 && rr < R && cc >= 0 && cc < C) {
                    if((arr[ll][rr][cc] == '.' || arr[ll][rr][cc] == 'E') && visited[ll][rr][cc] != 1) {
                        visited[ll][rr][cc] = 1;
                        q.push({ ll,rr,cc,cnt + 1 });
                    }
                }
            }
        }
 
        if (ans == 0) {
            printf("Trapped!\n");
        }
        else {
            printf("Escaped in %d minute(s).\n", ans);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1818번 - 책정리 (C++)  (0) 2022.12.20
[ 백준 ] 22255번 - 호석사우루스 (C++)  (0) 2022.12.19
[ 백준 ] 12014번 - 주식 (C++)  (0) 2022.12.17
[ 백준 ] 1365번 - 꼬인 전깃줄 (C++)  (0) 2022.12.16
[ 백준 ] 16397번 - 탈출 (C++)  (0) 2022.12.15
반응형

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

 

16397번: 탈출

첫 번째 줄에 N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), G (0 ≤ G ≤ 99,999)가 공백 하나를 사이에 두고 주어진다. 각각 N은 LED로 표현된 수, T는 버튼을 누를 수 있는 최대 횟수, G는 탈출을 위해 똑같이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited 배열을 만들어서 해당 숫자가 만들어진 적이 있는지 체크합니다.

 

2. bfs를 이용하여 버튼을 누를 때마다 queue에 숫자와 버튼을 누른 횟수를 push 합니다.

 

3. 현재 숫자가 G와 일치하면 cnt를 출력하고, queue가 빌 때까지 G와 같지 않다면 ANG를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, T, G;
int visited[100001];
 
int buttonB(int num)
{
    num *= 2;
 
    int temp = 100000;
 
    while (num < temp) temp /= 10;
 
    num -= temp;
 
    return num;
}
 
int main()
{
    scanf("%d %d %d", &N, &T, &G);
 
    queue<pair<int, int>>q;
 
    q.push({ N,0 });
 
    while (!q.empty()) {
        const int cur = q.front().first;
        const int cnt = q.front().second;
        q.pop();
 
        if (visited[cur] == 1 || cur > 99999 || cnt > T) continue;
        visited[cur] = 1;
 
        if (cur == G) {
            printf("%d", cnt);
            return 0;
        }
 
        if (visited[cur + 1] != 1) {
            q.push({ cur + 1,cnt + 1 });
        }
 
        if (cur < 50000) {
            const int B = buttonB(cur);
 
            if (visited[B]!=1) {
                q.push({ B,cnt + 1 });
            }
        }
    }
 
    printf("ANG");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 12014번 - 주식 (C++)  (0) 2022.12.17
[ 백준 ] 1365번 - 꼬인 전깃줄 (C++)  (0) 2022.12.16
[ 백준 ] 2812번 - 크게 만들기 (C++)  (0) 2022.12.14
[ 백준 ] 9019번 - DSLR (C++)  (0) 2022.12.13
[ 백준 ] 2665번 - 미로만들기 (C++)  (0) 2022.12.12
반응형

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

 

9019번: DSLR

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. A와 B를 입력받아서 저장합니다.

 

2. 각 문자에 맞게 변환하는 함수를 만듭니다.

 

3. bfs를 돌며 string에 현재까지 입력된 명령어들을 저장하면서 queue에 넣어줍니다.

 

4. A 와 B가 같아지면 string을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#include<string>
 
using namespace std;
 
struct node {
    int cur;
    string reg;
};
 
int left(int A)
{
    A *= 10;
    A += A / 10000;
    A %= 10000;
 
    return A;
}
 
int right(int A)
{
    int temp = A % 10;
    A /= 10;
    A += temp * 1000;
 
    return A;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int A, B;
        int visited[10000] = { 0 };
 
        scanf("%d %d", &A, &B);
 
        queue<node> q;
        string vect;
 
        q.push({ A,  vect});
        visited[A] = 1;
 
        while (!q.empty()) {
            int cur = q.front().cur;
            string str = q.front().reg;
            q.pop();
 
            if (cur == B) {
                for (auto next : str) {
                    printf("%c", next);
                }
                printf("\n");
                break;
            }
 
            vector<char> temp;
            int l = left(cur);
            int r = right(cur);
            int d = (cur * 2) % 10000;
            int s = (cur + 9999) % 10000;
            if (visited[l] != 1) {
                visited[l] = 1;
                q.push({ l, str+'L'});
            }
            if (visited[r] != 1) {
                visited[r] = 1;
                q.push({ r, str+'R'});
            }
            if (visited[d] != 1) {
                visited[d] = 1;
                q.push({ d, str+'D'});
            }
            if (visited[s] != 1) {
                visited[s] = 1;
                q.push({s, str+'S'});
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 16397번 - 탈출 (C++)  (0) 2022.12.15
[ 백준 ] 2812번 - 크게 만들기 (C++)  (0) 2022.12.14
[ 백준 ] 2665번 - 미로만들기 (C++)  (0) 2022.12.12
[ 백준 ] 1726번 - 로봇 (C++)  (0) 2022.12.11
[ 백준 ] 24042번 - 횡단보도 (C++)  (0) 2022.12.10
반응형

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

 

2665번: 미로만들기

첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dijkstra를 이용하여 흰 방을 지날 때의 가중치는 1, 검은 방을 지날 때는 가중치 10000을 주어서 도착점에 도착했을 때 이동 거리를 10000으로 나눈 값을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int n;
char arr[51][51];
int visited[50][50];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
struct node {
    int y;
    int x;
    int dist;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.dist < right.dist;
    }
};
 
int main()
{
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%s", arr[i]);
        for (int j = 0; j < n; j++) {
            visited[i][j] = 987654321;
        }
    }
 
    priority_queue<node, vector<node>, cmp> pq;
 
    pq.push({ 0,0,0 });
    visited[0][0] = 0;
 
    while (!pq.empty()) {
        const int y = pq.top().y;
        const int x = pq.top().x;
        const int dist = pq.top().dist;
        pq.pop();
 
        if (y == n - 1 && x == n - 1) {
            printf("%d", dist / 10000);
        }
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < n && xx >= 0 && xx < n) {
                if (arr[yy][xx] == '1') {    //흰 방
                    if (visited[yy][xx] > dist + 1) {
                        visited[yy][xx] = dist + 1;
                        pq.push({ yy,xx,dist + 1 });
                    }
                }
                else {        //검은 방
                    if (visited[yy][xx] > dist + 10000) {
                        visited[yy][xx] = dist + 10000;
                        pq.push({ yy,xx,dist + 10000 });
                    }
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2812번 - 크게 만들기 (C++)  (0) 2022.12.14
[ 백준 ] 9019번 - DSLR (C++)  (0) 2022.12.13
[ 백준 ] 1726번 - 로봇 (C++)  (0) 2022.12.11
[ 백준 ] 24042번 - 횡단보도 (C++)  (0) 2022.12.10
[ 백준 ] 1600번 - 말이 되고픈 원숭이 (C++)  (0) 2022.12.09

+ Recent posts

티스토리툴바