반응형

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

 

6087번: 레이저 통신

크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 맵을 입력받고, 문의 위치를 vector에 저장합니다.

 

2. visited [ y ][ x ][ dir ] 배열을 만들어 방문 여부를 저장합니다.

 

3. pos struct를 만들어 y좌표, x좌표, 빛의 방향, 거울의 개수를 저장합니다.

 

4. dijkstra를 이용하여 거울의 개수가 적은 순으로 priority_queue에서 뽑고, '.'을 만나면 pq에 넣습니다.

 

5. vector에 저장된 문의 좌표와 현재 좌표가 일치하면 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
#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
int W, H;
char arr[101][101];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int visited[101][101][4];
vector<pair<int, int>> laser;
 
struct pos {
    int y;
    int x;
    int cnt;
    int dir;
};
 
struct cmp {
    bool operator()(pos right, pos left) {
        return left.cnt < right.cnt;
    }
};
 
int main()
{
    scanf("%d %d", &W, &H);
 
    for (int i = 0; i < H; i++) {
        scanf("%s", arr[i]);
    }
 
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (arr[i][j] == 'C') {
                laser.emplace_back(i, j);
            }
        }
    }
 
    priority_queue<pos, vector<pos>, cmp> pq;
    for (int i = 0; i < 4; i++) {
        pq.push({ laser[0].first, laser[0].second, 0, i });
    }
 
    while (!pq.empty()) {
        const int y = pq.top().y;
        const int x = pq.top().x;
        const int cnt = pq.top().cnt;
        const int dir = pq.top().dir;
        pq.pop();
 
        if (visited[y][x][dir] == 1) continue;
        visited[y][x][dir] = 1;
 
        if (y == laser[1].first && x == laser[1].second) {
            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 < H && xx >= 0 && xx < W) {
                if (arr[yy][xx] == '*') continue;
                if (visited[yy][xx][dir] != 1) {
                    if (i != dir) {
                        pq.push({ yy,xx,cnt + 1,i });
                    }
                    else {
                        pq.push({ yy,xx,cnt,i });
                    }
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 15591번 - MooTube (Silver) (C++)  (0) 2022.11.26
[ 백준 ] 4991번 - 로봇 청소기 (C++)  (0) 2022.11.25
[ 백준 ] 4485번 - 녹색 옷 입은 애가 젤다지? (C++)  (0) 2022.11.23
[ 백준 ] 2151번 - 거울 설치 (C++)  (0) 2022.11.22
[ 백준 ] 17386번 - 선분 교차 1 (C++)  (0) 2022.11.21
반응형

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

 

2151번: 거울 설치

첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 맵을 입력받고, 문의 위치를 vector에 저장합니다.

 

2. pos struct를 만들어 y좌표, x좌표, 빛의 방향, 거울의 개수를 저장합니다.

 

3. visited배열에 방문 여부를 저장하고, visited [ i ][ j ][ k ]에서 i는 y좌표, j는 x좌표, k는 빛의 방향입니다.

 

4. dijkstra를 이용하여 거울의 개수가 적은 순으로 priority_queue에서 뽑고, '!'와 '#'를 만나면 pq에 넣습니다.

 

5. vector에 저장된 문의 좌표와 현재 좌표가 일치하면 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
83
84
85
86
87
88
89
90
91
#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
int N;
char arr[51][51];
int visited[51][51][4];
vector<pair<int, int>> door;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
struct pos {
    int y;
    int x;
    int cnt;
    int dir;
};
 
struct cmp {
    bool operator()(pos right, pos left) {
        return left.cnt < right.cnt;
    }
};
 
int main()
{
    scanf("%d", &N);
 
    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++) {
            if (arr[i][j] == '#') {
                door.emplace_back(i, j);
            }
        }
    }
 
    int y = door[0].first;
    int x = door[0].second;
 
    priority_queue<pos, vector<pos>, cmp> pq;
 
    for (int i = 0; i < 4; i++) {
        pq.push({ y,x,0,i });
    }
 
    while (!pq.empty()) {
        int y = pq.top().y;
        int x = pq.top().x;
        int cnt = pq.top().cnt;
        int dir = pq.top().dir;
        pq.pop();
 
        if (y == door[1].first && x == door[1].second) {
            printf("%d", cnt);
            return 0;
        }
 
        if (visited[y][x][dir] == 1) continue;
        visited[y][x][dir] = 1;
 
        for (int i = 1; i < N; i++) {
            int yy = y + dy[dir] * i;
            int xx = x + dx[dir] * i;
 
            if (arr[yy][xx] == '*' || yy >= N || yy < 0 || xx >= N || xx < 0) break;
            if (arr[yy][xx] == '!') {
                if (dir == 0 || dir == 1) {
                    if (visited[yy][xx][dir] != 1) {
                        pq.push({ yy,xx,cnt+1,2 });
                        pq.push({ yy,xx,cnt+1,3 });
                    }
                }
                else {
                    if (visited[yy][xx][dir] != 1) {
                        pq.push({ yy,xx,cnt+1,0 });
                        pq.push({ yy,xx,cnt+1,1 });
                    }
                }
            }
            if (arr[yy][xx] == '#') {
                pq.push({ yy,xx,cnt });
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 6087번 - 레이저 통신 (C++)  (0) 2022.11.24
[ 백준 ] 4485번 - 녹색 옷 입은 애가 젤다지? (C++)  (0) 2022.11.23
[ 백준 ] 17386번 - 선분 교차 1 (C++)  (0) 2022.11.21
[ 백준 ] 1774번 - 우주신과의 교감 (C++)  (0) 2022.11.20
[ 백준 ] 10282번 - 해킹 (C++)  (0) 2022.11.19
반응형

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

 

5529번: 저택

첫째 줄에 집의 크기 M, N과 스위치가 있는 방의 수 K가 주어진다. 둘째 줄부터 K개 줄에는 스위치가 있는 방의 위치 (xi, yi)가 주어진다. (2 ≤ M,N ≤ 100,000, 1 ≤ K ≤ 200,000)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각각의 x, y 좌표에 있는 버튼들을 sero, garo 배열에 저장합니다.

 

2. 각각의 sero, garo 배열을 오름차순으로 정렬 후 인접해 있는 점끼리 간선으로 연결합니다.

 

3. 버튼을 누르면 1분이 경과하므로 버튼끼리 거리 1인 간선으로 연결해 줍니다.

 

4. 출발점을 1, 0으로 두고 노드를 추가합니다. 그리고 도착점인 M, N도 노드에 추가합니다.

 

5. 데이크스트라를 이용하여 가장 빨리 도착할 수 있는 시간을 출력합니다.

 

[ 소스코드 ]

 

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
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<fstream>
#define INF 0x3f3f3f3f3f3f3f3f
 
using namespace std;
 
int N, M, K;
vector<pair<int, int>> sero[100002];    //특정 x좌표의 버튼을 저장할 배열
vector<pair<int, int>> garo[100002];    //특정 y좌표의 버튼을 저장할 배열
vector<pair<int, long long>> graph[400015];        //버튼간 연결되는 간선 저장
long long dist[400015];        //각 버튼까지 도착했을 때까지 걸린 시간 저장
 
int main()
{
    //freopen("input.txt", "r", stdin);
 
    scanf("%d %d %d", &M, &N, &K);
 
    bool E = true;
 
    for (int i = 0; i <= (K+ 1) * 2 + 1; i++) {
        dist[i] = INF;
    }
 
    for (int i = 1; i <= K; i++) {
        int m, n;
        scanf("%d %d", &m, &n);
 
        sero[m].emplace_back(n, i);
        garo[n].emplace_back(m, i);
    }
    sero[1].emplace_back(0, 0);        //1,0 좌표에서 출발
 
    sero[M].emplace_back(N, K + 1);    //도착지
    garo[N].emplace_back(M, K + 1);
 
    for (int i = 1; i <= K; i++) {    //방향 변경시 버튼을 누르면 1분 경과
        graph[i * 2].emplace_back(i * 2 + 1, 1);
        graph[i * 2 + 1].emplace_back(i * 2, 1);
    }
 
    for (int i = 1; i <= N; i++) {
        sort(garo[i].begin(), garo[i].end());
    }
    for (int i = 1; i <= M; i++) {
        sort(sero[i].begin(), sero[i].end());
    }
 
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j < (int)garo[i].size() - 1; j++) {
            const int dist = garo[i][j + 1].first - garo[i][j].first;
            const int u = garo[i][j + 1].second;
            const int v = garo[i][j].second;
            graph[u * 2].emplace_back(v * 2, dist);        //가로 방향 간선 연결
            graph[v * 2].emplace_back(u * 2, dist);
        }
    }
 
    for (int i = 0; i <= M; i++) {
        for (int j = 0; j < (int)sero[i].size() - 1; j++) {
            const int dist = sero[i][j + 1].first - sero[i][j].first;
            const int u = sero[i][j + 1].second;
            const int v = sero[i][j].second;
            graph[u * 2 + 1].emplace_back(v * 2 + 1, dist);    //세로 방향 간선 연결
            graph[v * 2 + 1].emplace_back(u * 2 + 1, dist);
        }
    }
 
    priority_queue<pair<long long,int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
 
    pq.push({-1,1});
    while (!pq.empty()) {
        const long long curDist = pq.top().first;
        const int curId = pq.top().second;
        pq.pop();
 
        if (dist[curId] < curDist) continue;
 
        for (auto &next : graph[curId]) {
            const int nextId = next.first;
            const long long nextDist = next.second;
 
            if (dist[nextId] > curDist + nextDist) {
                dist[nextId] = curDist + nextDist;
                pq.push({ dist[nextId], nextId });
            }
        }
    }
 
    if (dist[(K + 1)*2] == INF && dist[(K+1)*2+1] == INF) {
        printf("%d", -1);
    }
    else {
        printf("%lld", min(dist[(K + 1) * 2], dist[(K + 1) * 2 + 1]));
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 10282번 - 해킹 (C++)  (0) 2022.11.19
[ 백준 ] 3584번 - 가장 가까운 공통 조상 (C++)  (0) 2022.11.18
[ 백준 ] 16933번 - 벽 부수고 이동하기 3 (C++)  (0) 2022.11.16
[ 백준 ] 11758번 - CCW (C++)  (0) 2022.11.15
[ 백준 ] 15681번 - 트리와 쿼리 (C++)  (0) 2022.11.14
반응형

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

 

16933번: 벽 부수고 이동하기 3

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 방문을 체크할 visited [1001][1001][11][2]를 만듭니다. (y, x, crash, day)

 

2. 낮일 때만 벽을 부술 수 있는 로직을 추가합니다.

 

3. 밤일 때 현재 자리에 벽이 있을 수 있으므로 분기를 추가해줍니다.

 

4. y == N, x == M일 때 cnt를 출력하고, 도착하지 못한다면 -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>
 
using namespace std;
 
struct pos {
    int y;        //y좌표
    int x;        //x좌표
    int cnt;    //이동 거리
    int crash;    //부순 벽 개수
    int day;    //0 : 밤, 1 : 낮
};
 
int N, M, K;
char arr[1002][1002];
int visited[1001][1001][11][2];        //visited[y][x][crash][day]
const int dy[5] = { 0,-1,1,0,0 };
const int dx[5] = { 0,0,0,-1,1 };
 
int main()
{
    scanf("%d %d %d", &N, &M, &K);
 
    for (int i = 1; i <= N; i++) {
        scanf("%s", &arr[i][1]);
    }
 
    queue<pos> q;
 
    q.push({ 1,1,1,0,1 });
    visited[1][1][0][1] = 1;
 
    while (!q.empty()) {
        const int y = q.front().y;
        const int x = q.front().x;
        const int cnt = q.front().cnt;
        const int crash = q.front().crash;
        const int day = q.front().day;
        q.pop();
 
        if (y == N && x == M) {
            printf("%d", cnt);
            return 0;
        }
 
        for (int i = 0; i < 5; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy > 0 && yy <= N && xx > 0 && xx <= M) {
                if (day == 0) {    //밤일 때
                    if (i == 0) {
                        if (arr[yy][xx] == '1' && visited[yy][xx][crash][1] != 1) {
                            visited[yy][xx][crash][1] = 1;
                            q.push({ yy,xx,cnt + 1,crash,1 });
                        }
                    }
                    if (arr[yy][xx] == '0' && visited[yy][xx][crash][1] != 1) {
                        visited[yy][xx][crash][1] = 1;
                        q.push({ yy,xx,cnt + 1,crash,1 });
                    }
                }
                else {    //낮일 때
                    if (i != 0) {
                        if (arr[yy][xx] == '0' && visited[yy][xx][crash][0] != 1) {
                            visited[yy][xx][crash][0] = 1;
                            q.push({ yy,xx,cnt + 1,crash,0 });
                        }
                        else if (arr[yy][xx] == '1' && crash < K) {
                            if (visited[yy][xx][crash + 1][0] != 1) {
                                visited[yy][xx][crash + 1][0] = 1;
                                q.push({ yy,xx,cnt + 1,crash + 1,0 });
                            }
                        }
                    }
                }
            }
        }
    }
 
    printf("%d", -1);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 3584번 - 가장 가까운 공통 조상 (C++)  (0) 2022.11.18
[ 백준 ] 5529번 - 저택 (C++)  (0) 2022.11.17
[ 백준 ] 11758번 - CCW (C++)  (0) 2022.11.15
[ 백준 ] 15681번 - 트리와 쿼리 (C++)  (0) 2022.11.14
[ 백준 ] 7682번 - 틱택토 (C++)  (0) 2022.11.13
반응형

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

 

13913번: 숨바꼭질 4

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

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. N이 K보다 클 경우 x - 1로 이동할 수밖에 없으므로 N부터 K까지 1씩 빼주면서 출력합니다.

 

2. 아닐 경우 bfs를 이용하여 이동하고, 어디로 부터 왔는지 from 배열에 저장합니다.

 

3. cur == K일 경우 from 배열을 체크하면서 어디서부터 왔는지 ans vector에 저장합니다.

 

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
#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
int N, K;
bool visited[200001];
int from[200001];
 
int main()
{
    scanf("%d %d", &N, &K);
 
    if (N > K) {    //N이 K보다 크다면 x-1로 밖에 이동할 수 없으므로
        printf("%d\n", N - K);
        for (int i = N; i >= K; i--) {
            printf("%d ", i);
        }
        return 0;
    }
 
    visited[N] = true;
 
    queue<int> q;
 
    q.push({ N });
 
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        if (cur == K) {
            vector<int> ans;    //이동 경로
            for (int i = K; i != N; i=from[i]) {
                ans.push_back(i);
            }
            printf("%d\n", ans.size());
            printf("%d ", N);
            for (int i = ans.size() - 1; i >= 0; i--) {
                printf("%d ", ans[i]);
            }
        }
 
        if (cur - 1 >= 0) {
            if (visited[cur - 1] != true) {
                visited[cur - 1] = true;
                from[cur - 1] = cur;    //어디로 부터 왔는지 이동한 위치에서 저장
                q.push(cur - 1);
            }
        }
        if (visited[cur + 1] != true && cur < K) {
            visited[cur + 1] = true;
            from[cur + 1] = cur;
            q.push(cur + 1);
        }
        if (cur <= K) {
            if (visited[cur * 2] != true) {
                visited[cur * 2] = true;
                from[cur * 2] = cur;
                q.push(cur * 2);
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 15681번 - 트리와 쿼리 (C++)  (0) 2022.11.14
[ 백준 ] 7682번 - 틱택토 (C++)  (0) 2022.11.13
[ 백준 ] 1976번 - 여행 가자 (C++)  (0) 2022.11.11
[ 백준 ] 12286번 - 돌 그룹 (C++)  (0) 2022.11.10
[ 백준 ] 2281번 - 데스노트 (C++)  (0) 2022.11.09
반응형

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

 

1976번: 여행 가자

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. bfs를 활용하여 갈 수 있는 도시들을 visited 배열에 저장합니다.

 

2. 가야 할 도시들을 for문으로 돌아가며 visited 배열에 있는지 체크하고, 없다면 "NO"를 출력하고, 그렇지 않으면 "YES"를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int arr[201][201];
int route[1000];
int visited[201];
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    for (int i = 0; i < M; i++) {
        scanf("%d", &route[i]);
    }
 
    queue<int> q;
    q.push(route[0]);
    visited[route[0]] = 1;
 
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        for (int i = 1; i <= N; i++) {
            if (visited[i] != 1 && arr[cur][i] == 1) {
                visited[i] = 1;
                q.push(i);
            }
        }
    }
 
    for (int i = 0; i < M; i++) {
        if (visited[route[i]] == 0) {
            printf("NO");
            return 0;
        }
    }
 
    printf("YES");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 7682번 - 틱택토 (C++)  (0) 2022.11.13
[ 백준 ] 13913번 - 숨바꼭질 4 (C++)  (0) 2022.11.12
[ 백준 ] 12286번 - 돌 그룹 (C++)  (0) 2022.11.10
[ 백준 ] 2281번 - 데스노트 (C++)  (0) 2022.11.09
[ 백준 ] 7569번 - 토마토 (C++)  (0) 2022.11.08
반응형

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

 

12886번: 돌 그룹

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 돌의 전체 합을 sum 변수에 저장합니다.

 

2. 상태를 저장할 visited [1501][1501] 배열을 만듭니다. A와 B만 저장하는 이유는 C = sum - A - B로 정의할 수 있기 때문입니다.

 

3. queue에 현재 상태를 넣고 for문을 돌리면서 stone [ i ] > stone [ j ] 일 경우 방문한 경우가 아닐 때 A = stone [ i ]-stone [ j ], B = stone [ j ] * 2로 저장하여 다시 queue에 넣어줍니다.

 

4. 위과정을 반복하다가 A == B && B == C일 경우 1을 출력해주고, 아닐 경우 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
#include<iostream>
#include<queue>
 
using namespace std;
 
int A, B, C;
int sum;
int visited[1501][1501];
 
int main()
{
    scanf("%d %d %d", &A, &B, &C);
 
    sum = A + B + C;
 
    if (sum% 3 != 0) {
        printf("%d", 0);
        return 0;
    }
 
    queue<pair<int, int>> q;
    q.push({ A,B });
    visited[A][B] = 1;
    visited[B][A] = 1;
 
    while (!q.empty()) {
        int A = q.front().first;
        int B = q.front().second;
        int C = sum - A - B;
        q.pop();
 
        if (A == B && B == C) {
            printf("%d", 1);
            return 0;
        }
 
        int stone[3] = { A,B,C };
 
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (stone[i] > stone[j]) {
                    int AA = stone[i] - stone[j];
                    int BB = stone[j] * 2;
 
                    if (visited[AA][BB] != 1 && visited[BB][AA] != 1) {
                        visited[AA][BB] = 1;
                        visited[BB][AA] = 1;
                        q.push({ AA,BB });
                    }
                }
            }
        }
    }
 
 
    printf("%d", 0);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 13913번 - 숨바꼭질 4 (C++)  (0) 2022.11.12
[ 백준 ] 1976번 - 여행 가자 (C++)  (0) 2022.11.11
[ 백준 ] 2281번 - 데스노트 (C++)  (0) 2022.11.09
[ 백준 ] 7569번 - 토마토 (C++)  (0) 2022.11.08
[ 백준 ] 2195번 - 문자열 복사 (C++)  (0) 2022.11.07
반응형

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

 

7569번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. tomato struct를 만들어서 z, y, x 좌표와 토마토가 익는 데 걸리는 시간 cnt를 저장합니다.

 

2. 1을 입력 받으면 queue에 z, y, x 좌표를 넣고, visited 배열을 1로 갱신해줍니다.

 

3. bfs를 이용해서 익지 않은 토마토가 인접해 있다면 1로 바꾸고, queue에 넣어줍니다.

 

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
#include<iostream>
#include<queue>
 
using namespace std;
 
struct tomato {
    int z;
    int y;
    int x;
    int cnt;
};
 
int N, M, H;
int arr[100][100][100];
int visited[100][100][100];
int dz[6] = { 0,0,0,0,-1,1 };
int dy[6] = { -1,1,0,0,0,0 };
int dx[6] = { 0,0,-1,1,0,0 };
int ans = -1;
queue<tomato> q;
 
 
bool check()
{
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < M; k++) {
                if (arr[i][j][k] == 0) {
                    return false;
                }
            }
        }
    }
 
    return true;
}
 
int main()
{
    scanf("%d %d %d", &M, &N, &H);
 
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < M; k++) {
                scanf("%d", &arr[i][j][k]);
 
                if (arr[i][j][k] == 1) {
                    q.push({ i,j,k,0 });
                    visited[i][j][k] = 1;
                }
            }
        }
    }
 
    if (check()) {
        printf("%d", 0);
        return 0;
    }
 
    while (!q.empty()) {
        int z = q.front().z;
        int y = q.front().y;
        int x = q.front().x;
        int cnt = q.front().cnt;
        q.pop();
 
        ans = max(ans, cnt);
 
        for (int i = 0; i < 6; i++) {
            int zz = z + dz[i];
            int yy = y + dy[i];
            int xx = x + dx[i];
 
            if (zz >= 0 && zz < H && yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (visited[zz][yy][xx] != 1 && arr[zz][yy][xx] == 0) {
                    arr[zz][yy][xx] = 1;
                    visited[zz][yy][xx] = 1;
                    q.push({ zz,yy,xx,cnt + 1 });
                }
            }
        }
    }
 
    if (check()) {
        printf("%d", ans);
    }
    else {
        printf("%d", -1);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 12286번 - 돌 그룹 (C++)  (0) 2022.11.10
[ 백준 ] 2281번 - 데스노트 (C++)  (0) 2022.11.09
[ 백준 ] 2195번 - 문자열 복사 (C++)  (0) 2022.11.07
[ 백준 ] 2253번 - 점프 (C++)  (0) 2022.11.06
[ 백준 ] 14002번 - 가장 긴 증가하는 부분 수열 4 (C++)  (0) 2022.11.05
반응형

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

 

2636번: 치즈

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 바깥쪽의 공기를 bfs를 이용하여 찾아줍니다.

 

2. 치즈를 for문을 통해 돌면서 공기 중에 노출되어 있다면 녹입니다.

 

3. 녹이기 전 치즈의 개수를 세어서 ans에 넣습니다.

 

4. 만약 치즈의 개수가 0개라면 흐른 시간과 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
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
#include<iostream>
#include<queue>
#include<cstring>
 
using namespace std;
 
int N, M;
int arr[100][100];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int temp[100][100];
int visited[100][100];
int ans;
int ansC;
 
bool check(int y, int x)    //공기 중에 노출 된 치즈 찾기
{
    for (int i = 0; i < 4; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
 
        if (temp[yy][xx] == 2) {
            return true;
        }
    }
 
    return false;
}
 
void bfs()        //공기를 찾는 bfs
{
    queue<pair<int, int>> q;
    q.push({ 0,0 });
    memset(temp, 0, sizeof(temp));
    memset(visited, 0, sizeof(visited));
    temp[0][0] = 2;
    visited[0][0] = 1;
 
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        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 (arr[yy][xx] == 0 && visited[yy][xx] != 1) {
                    visited[yy][xx] = 1;
                    temp[yy][xx] = 2;
                    q.push({ yy,xx });
                }
            }
        }
    }
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    while (1) {
        bfs();
        int cnt = 0;
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 1) {
                    cnt++;
                    if (check(i, j)) {
                        temp[i][j] = 1;
                    }
                }
            }
        }
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (temp[i][j] == 1) {
                    arr[i][j] = 0;
                }
            }
        }
        
        if (cnt == 0) {
            printf("%d\n%d", ansC, ans);
            return 0;
        }
 
        ans = cnt;
        ansC++;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2011번 - 암호코드 (C++)  (0) 2022.10.20
[ 백준 ] 2631번 - 줄세우기 (C++)  (0) 2022.10.19
[ 백준 ] 3954번 - Brainf**k 인터프리터 (C++)  (0) 2022.10.15
[ 백준 ] 15486번 - 퇴사 2 (C++)  (0) 2022.10.14
[ 백준 ] 14442번 - 벽 부수고 이동하기 2 (C++)  (0) 2022.10.13
반응형

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

 

14442번: 벽 부수고 이동하기 2

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 방문 배열 visited [ 1000 ][ 1001 ][ 10 ]을 만들어 벽을 부순 개수에 따라 방문을 체크합니다.

 

2. bfs를 활용하여 도착지점에 도착하면 움직인 횟수를 출력하고 도착하지 못하면 -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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M, K;
char arr[1000][1001];
int visited[1000][1000][10];    //부순 벽의 개수에 따라 방문을 다르게 해줌
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
struct pos {
    int y;
    int x;
    int cnt;
    int cntW;
};
 
int main()
{
    scanf("%d %d %d", &N, &M, &K);
 
    for (int i = 0; i < N; i++) {
        scanf("%s", arr[i]);
    }
 
    queue<pos> q;
    q.push({ 0,0,1,0 });
    visited[0][0][0] = 1;
 
    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        int cnt = q.front().cnt;
        int cntW = q.front().cntW;
        q.pop();
 
        if (y == N - 1 && x == M - 1) {
            printf("%d", cnt);
            return 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 (arr[yy][xx] == '0' && visited[yy][xx][cntW] != 1) {    //벽이 아닐 때
                    visited[yy][xx][cntW] = 1;
                    q.push({ yy,xx,cnt + 1,cntW });
                }
                else if (arr[yy][xx] == '1' && visited[yy][xx][cntW + 1] != 1 && cntW < K) {    //벽일 때
                    visited[yy][xx][cntW + 1] = 1;
                    q.push({ yy,xx,cnt + 1,cntW + 1 });
                }
            }
        }
    }
 
    printf("%d", -1);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 3954번 - Brainf**k 인터프리터 (C++)  (0) 2022.10.15
[ 백준 ] 15486번 - 퇴사 2 (C++)  (0) 2022.10.14
[ 백준 ] 17472번 - 다리 만들기 2 (C++)  (0) 2022.10.12
[ 백준 ] 1956번 - 운동 (C++)  (0) 2022.10.11
[ 백준 ] 23291번 - 어항 정리 (C++)  (0) 2022.10.10

+ Recent posts

티스토리툴바