반응형

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

 

1726번: 로봇

많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 로봇의 시작점과 도착점을 입력받아서 저장합니다.

 

2. 로봇의 시작점을 queue에 넣고 bfs를 돌리면서 visited [ y ][ x ][ dir ] 배열에 현재까지의 명령어 입력 횟수를 저장합니다.

 

3. 도착점에 도착하면 방향의 일치 여부를 판단하고 일치하면 cnt를 ans의 값과 비교하여 더 작은 값을 ans에 저장하고, 다르다면 방향에 따라 cnt에 1 ~ 2를 더해주어 ans의 값과 비교하여 더 작은 값을 ans에 저장합니다.

 

4. 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
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
#include<iostream>
#include<queue>
 
using namespace std;
 
struct robot {
    int y;
    int x;
    int dir;
    int cnt;
};
 
int N, M;
int arr[101][101];
int visited[101][101][5];
int dy[5] = { 0,0,0,1,-1 };
int dx[5] = { 0,1,-1,0,0 };
int ans = 987654321;
 
int main()
{
    scanf("%d %d", &M, &N);
 
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &arr[i][j]);
            for (int k = 1; k <= 4; k++) {
                visited[i][j][k] = 987654321;
            }
        }
    }
 
    robot start, end;
 
    scanf("%d %d %d", &start.y, &start.x, &start.dir);
    scanf("%d %d %d", &end.y, &end.x, &end.dir);
 
    queue<robot> q;
 
    q.push({ start.y, start.x, start.dir, 0 });
 
    while (!q.empty()) {
        const int y = q.front().y;
        const int x = q.front().x;
        const int dir = q.front().dir;
        int cnt = q.front().cnt;
        q.pop();
        
        if (y == end.y && x == end.x) {
            if (dir != end.dir) {
                if (dir == 1 || dir == 2) {
                    if (end.dir == 3 || end.dir == 4) {
                        cnt += 1;
                    }
                    else {
                        cnt += 2;
                    }
                }
                else {
                    if (end.dir == 1 || end.dir == 2) {
                        cnt += 1;
                    }
                    else {
                        cnt += 2;
                    }
                }
            }
            
            ans = min(ans, cnt);
        }
 
        for (int i = 0; i < 4; i++) {
            for (int j = 1; j <= 3; j++) {
                int temp = dir + i;
                if (temp > 4) {
                    temp -= 4;
                }
                int yy = y + dy[temp]*j;
                int xx = x + dx[temp]*j;
 
                if (yy > 0 && yy <= M && xx > 0 && xx <= N) {
                    if (arr[yy][xx] == 0) {
                        if (i == 0) {
                            if (visited[yy][xx][temp] > cnt + 1) {
                                visited[yy][xx][temp] = cnt + 1;
                                q.push({ yy,xx,temp,cnt + 1 });
                            }
                        }
                        else {
                            if (dir == 1 || dir == 3) {
                                if (i == 1) {
                                    if (visited[yy][xx][temp] > cnt + 3) {
                                        visited[yy][xx][temp] = cnt + 3;
                                        q.push({ yy,xx,temp,cnt + 3 });
                                    }
                                }
                                else if (i == 2 || i == 3) {
                                    if (visited[yy][xx][temp] > cnt + 2) {
                                        visited[yy][xx][temp] = cnt + 2;
                                        q.push({ yy,xx,temp,cnt + 2 });
                                    }
                                }
                            }
                            else {
                                if (i == 3) {
                                    if (visited[yy][xx][temp] > cnt + 3) {
                                        visited[yy][xx][temp] = cnt + 3;
                                        q.push({ yy,xx,temp,cnt + 3 });
                                    }
                                }
                                else if (i == 1 || i == 2) {
                                    if (visited[yy][xx][temp] > cnt + 2) {
                                        visited[yy][xx][temp] = cnt + 2;
                                        q.push({ yy,xx,temp,cnt + 2 });
                                    }
                                }
                            }
                        }
                    }
                    else break;
                }
                else break;
            }
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 9019번 - DSLR (C++)  (0) 2022.12.13
[ 백준 ] 2665번 - 미로만들기 (C++)  (0) 2022.12.12
[ 백준 ] 24042번 - 횡단보도 (C++)  (0) 2022.12.10
[ 백준 ] 1600번 - 말이 되고픈 원숭이 (C++)  (0) 2022.12.09
[ 백준 ] 16393번 - Lost Map (C++)  (0) 2022.12.08
반응형

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

 

1600번: 말이 되고픈 원숭이

첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 방문을 기록할 visited [ i ][ j ][ k ]를 만듭니다. 여기서 k는 말처럼 이동한 횟수입니다.

 

2. bfs를 이용하여 말처럼 이동 횟수가 K번 미만이라면 인접한 곳, 말처럼 이동합니다.

 

3. 만약 W-1, H-1의 좌표에 도착하면 여태 이동했던 횟수를 출력합니다.

 

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int K, W, H;
int arr[200][200];
int visited[200][200][31];
int dy[4] = { -1,1,0,0 };    //인접
int dx[4] = { 0,0,-1,1 };
int dyy[8] = { -2,-1,1,2,2,1,-1,-2 };    //말처럼
int dxx[8] = { 1,2,2,1,-1,-2,-2,-1 };
 
struct node {
    int y;
    int x;
    int k;
    int cnt;
};
 
int main()
{
    scanf("%d %d %d", &K, &W, &H);
 
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    queue<node> q;
 
    q.push({ 0,0,0,0 });
    visited[0][0][0] = 1;
 
    while (!q.empty()) {
        const int y = q.front().y;
        const int x = q.front().x;
        const int k = q.front().k;
        const int cnt = q.front().cnt;
        q.pop();
 
        if (y == H - 1 && x == W - 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 < H && xx >= 0 && xx < W) {    // 인접한 곳으로 이동
                if (visited[yy][xx][k] != 1 && arr[yy][xx] == 0) {
                    visited[yy][xx][k] = 1;
                    q.push({ yy,xx,k,cnt+1 });
                }
            }
        }
 
        if (k < K) {
            for (int i = 0; i < 8; i++) {    //말처럼 이동
                const int yy = y + dyy[i];
                const int xx = x + dxx[i];
 
                if (yy >= 0 && yy < H && xx >= 0 && xx < W) {
                    if (visited[yy][xx][k + 1] != 1 && arr[yy][xx] == 0) {
                        visited[yy][xx][k + 1] = 1;
                        q.push({ yy,xx,k + 1,cnt+1 });
                    }
                }
            }
        }
    }
 
    printf("%d", -1);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1726번 - 로봇 (C++)  (0) 2022.12.11
[ 백준 ] 24042번 - 횡단보도 (C++)  (0) 2022.12.10
[ 백준 ] 16393번 - Lost Map (C++)  (0) 2022.12.08
[ 백준 ] 1016번 - 제곱 ㄴㄴ 수 (C++)  (0) 2022.12.07
[ 백준 ] 6091번 - 핑크 플로이드 (C++)  (0) 2022.12.06
반응형

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

 

5427번: 불

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. queue에 불의 좌표를 먼저 넣습니다.

 

2. 상근이의 좌표를 queue에 넣습니다.

 

3. bfs를 돌면서 불을 먼저 이동시키고 이후 상근이를 이동시키면서 상근이가 범위 밖으로 벗어나면 현재까지 이동한 거리를 출력합니다.

 

4. queue가 빌 때까지 지훈이가 탈출하지 못하면 IMPOSSIBLE을 출력합니다.

 

[ 소스코드 ]

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<cstring>
 
using namespace std;
 
char arr[1001][1001];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int visited[1000][1000];
int w, h;
 
struct node {
    int y;
    int x;
    int cur;
    int cnt;
};
 
void bfs(queue<node> q)
{
    while (!q.empty()) {
        const int y = q.front().y;
        const int x = q.front().x;
        const int cur = q.front().cur;
        const int cnt = q.front().cnt;
        q.pop();
 
        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 (cur == 1) {
                    if (arr[yy][xx] == '.' || arr[yy][xx] == '@') {
                        arr[yy][xx] = '*';
                        q.push({ yy,xx,cur,cnt });
                    }
                }
                else {
                    if (visited[yy][xx] != 1 && arr[yy][xx] == '.') {
                        visited[yy][xx] = 1;
                        q.push({ yy,xx,cur,cnt + 1 });
                    }
                }
            }
            else {
                if (cur == 0) {
                    printf("%d\n", cnt + 1);
                    return;
                }
            }
        }
    }
 
    printf("IMPOSSIBLE\n");
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        memset(visited, 0, sizeof(visited));
        int y, x;
        scanf("%d %d", &w, &h);
        queue<node> q;
 
        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] == '*') {
                    q.push({ i,j,1,0 });
                }
                if (arr[i][j] == '@') {
                    y = i;
                    x = j;
                }
            }
        }
 
        q.push({ y,x,0,0 });
        visited[y][x] = 1;
 
        bfs(q);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1016번 - 제곱 ㄴㄴ 수 (C++)  (0) 2022.12.07
[ 백준 ] 6091번 - 핑크 플로이드 (C++)  (0) 2022.12.06
[ 백준 ] 4179번 - 불! (C++)  (0) 2022.12.04
[ 백준 ] 10159번 - 저울 (C++)  (0) 2022.12.03
[ 백준 ] 14466번 - 소가 길을 건너간 이유 6 (C++)  (0) 2022.12.02
반응형

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

 

4179번: 불!

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다.  각각의 문

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. queue에 불의 좌표를 먼저 넣습니다.

 

2. 지훈이의 좌표를 queue에 넣습니다.

 

3. bfs를 돌면서 불을 먼저 이동시키고 이후 지훈이를 이동시키면서 지훈이가 범위 밖으로 벗어나면 현재까지 이동한 거리를 출력합니다.

 

4. queue가 빌 때까지 지훈이가 탈출하지 못하면 IMPOSSIBLE을 출력합니다.

 

[ 소스코드 ]

 

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

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

[ 백준 ] 6091번 - 핑크 플로이드 (C++)  (0) 2022.12.06
[ 백준 ] 5427번 - 불 (C++)  (0) 2022.12.05
[ 백준 ] 10159번 - 저울 (C++)  (0) 2022.12.03
[ 백준 ] 14466번 - 소가 길을 건너간 이유 6 (C++)  (0) 2022.12.02
[ 백준 ] 1039번 - 교환 (C++)  (0) 2022.12.01
반응형

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

 

10159번: 저울

첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. arr [ i ][ j ]에서 [ i ] > [ j ]라면 2, [ i ] < [ j ]라면 1로 저장합니다.

 

2. 1에서 N까지 for문을 돌면서 bfs를 통해 무게를 비교 가능하다면 cnt [ i ]에 값을 저장합니다.

 

3. N - cnt[ i ] - 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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int arr[101][101];
int cnt[101];
 
int main()
{
    scanf("%d %d", &N, &M);
    
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        arr[a][b] = 2;
        arr[b][a] = 1;
    }
 
    for (int i = 1; i <= N; i++) {
        int visited[101] = { 0 };
 
        queue<pair<int, int>> q;
        visited[i] = 1;
 
        for (int j = 1; j <= N; j++) {
            if (arr[i][j] != 0) {
                q.push({ j,arr[i][j] });
                cnt[i]++;
                visited[j] = 1;
            }
        }
 
        while (!q.empty()) {
            const int cur = q.front().first;
            const int ineq = q.front().second;
            q.pop();
 
            for (int j = 1; j <= N; j++) {
                if (visited[j] != 1 && arr[cur][j] == ineq) {
                    visited[j] = 1;
                    q.push({ j,ineq });
                    cnt[i]++;
                }
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        printf("%d\n", N - cnt[i] - 1);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 5427번 - 불 (C++)  (0) 2022.12.05
[ 백준 ] 4179번 - 불! (C++)  (0) 2022.12.04
[ 백준 ] 14466번 - 소가 길을 건너간 이유 6 (C++)  (0) 2022.12.02
[ 백준 ] 1039번 - 교환 (C++)  (0) 2022.12.01
[ 백준 ] 1669번 - 멍멍이 쓰다듬기 (C++)  (0) 2022.11.30
반응형

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

 

14466번: 소가 길을 건너간 이유 6

첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. road[ r + r` ][ c + c` ] 배열을 만들어 길의 위치를 저장합니다.

 

2. cow 배열을 만들어 소들의 위치를 저장합니다.

 

3. for문을 통해 cow 배열을 돌면서 bfs를 이용하여 몇마리의 소를 만날 수 있는지 ans에 저장합니다.

 

4. ans는 만날 수 있는 모든 경우이므로 겹치는 경우를 빼기 위해 2로 나눈 후, 나올 수 있는 모든 쌍에서 ans/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
#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
int N, K, R;
int road[205][205];
int arr[101][101];
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
vector<pair<int, int>> cow;
 
int bfs(int num)
{
    int ret = 0;
    int visited[101][101] = { 0 };
    queue<pair<int, int>> q;
    q.push({ cow[num].first, cow[num].second });
 
    while (!q.empty()) {
        const int r = q.front().first;
        const int c = q.front().second;
        q.pop();
 
        if (visited[r][c] == 1) continue;
        visited[r][c] = 1;
 
        if (arr[r][c] == 1) {
            ret++;
        }
 
        for (int i = 0; i < 4; i++) {
            const int rr = r + dr[i];
            const int cc = c + dc[i];
 
            if (rr > 0 && rr <= N && cc > 0 && cc <= N) {
                if (road[r + rr][c + cc] != 1) {
                    q.push({ rr,cc });
                }
            }
        }
    }
 
    return ret - 1;
}
 
int main()
{
    scanf("%d %d %d", &N, &K, &R);
 
    for (int i = 0; i < R; i++) {
        int r, c, rr, cc;
        scanf("%d %d %d %d", &r, &c, &rr, &cc);
 
        road[r + rr][c + cc] = 1;    //길의 위치
    }
 
    for (int i = 0; i < K; i++) {
        int r, c;
        scanf("%d %d", &r, &c);
 
        arr[r][c] = 1;
        cow.emplace_back(r, c);
    }
 
    int pair = (K) * (K - 1) / 2;    //나올 수 있는 모든 쌍
 
    int ans = 0;    //길 없이 만날 수 있는 모든 쌍의 수
 
    for (int i = 0; i < cow.size(); i++) {
        ans += bfs(i);
    }
 
    printf("%d", pair - ans / 2);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 4179번 - 불! (C++)  (0) 2022.12.04
[ 백준 ] 10159번 - 저울 (C++)  (0) 2022.12.03
[ 백준 ] 1039번 - 교환 (C++)  (0) 2022.12.01
[ 백준 ] 1669번 - 멍멍이 쓰다듬기 (C++)  (0) 2022.11.30
[ 백준 ] 11967번 - 불켜기 (C++)  (0) 2022.11.29
반응형

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

 

1039번: 교환

첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. N의 값이 10보다 작으면 -1을 츨력합니다.

 

2. n번 연산을 진행했을 때 숫자의 방문 여부를 체크할 visited [ num ][ n ] 배열을 만듭니다.

 

3. bfs를 활용하여 각각의 자릿수를 바꾸고 queue에 넣으면서 방문 처리를 해줍니다.

 

4. 교환 중 제일 앞자리 숫자가 0이 되면 안되므로 continue 해줍니다.

 

5. K번 연산을 진행했을 때 최댓값을 ans에 저장합니다.

 

6. 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
#include<iostream>
#include<queue>
#include<cmath>
 
using namespace std;
 
int N, K;
int visited[1000001][11];
 
struct node {
    vector<int> num;
    int cnt;
};
 
int getDigit(int num)
{
    int ret = 1;
 
    while (1) {
        if (num < pow(10, ret)) {
            return ret;
        }
        ret++;
    }
}
 
int main()
{
    scanf("%d %d", &N, &K);
 
    vector<int> num;
 
    if (N < 10) {
        printf("%d", -1);
        return 0;
    }
 
    int digit = getDigit(N);
 
    num.resize(digit);
 
    for (int i = digit-1; i >= 0; i--) {
        num[i] = N / pow(10, i);
        N %= (int)pow(10, i);
    }
 
    queue<node> q;
 
    q.push({ num,0 });
 
    int ans = -1;
 
    while (!q.empty()) {
        vector<int> cur = q.front().num;
        vector<int> a = q.front().num;
        int cnt = q.front().cnt;
        q.pop();
        int num = 0;
 
        if (cur[digit - 1] == 0) continue;
        if (cnt > K) continue;
 
        for (int i = 0; i < digit; i++) {
            num += cur[i] * pow(10, i);
        }
 
        if (visited[num][cnt] == 1) continue;
        visited[num][cnt] = 1;
 
        if (cnt == K) {
            ans = max(ans, num);
        }
 
        for (int i = 0; i < digit - 1; i++) {
            for (int j = i + 1; j < digit; j++) {
                if (i != j) {
                    cur = a;
                    int temp = cur[i];
                    cur[i] = cur[j];
                    cur[j] = temp;
 
                    q.push({ cur,cnt + 1 });
                }
            }
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 10159번 - 저울 (C++)  (0) 2022.12.03
[ 백준 ] 14466번 - 소가 길을 건너간 이유 6 (C++)  (0) 2022.12.02
[ 백준 ] 1669번 - 멍멍이 쓰다듬기 (C++)  (0) 2022.11.30
[ 백준 ] 11967번 - 불켜기 (C++)  (0) 2022.11.29
[ 백준 ] 2550번 - 전구 (C++)  (0) 2022.11.28
반응형

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

 

11967번: 불켜기

(1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. bfs를 이용하여 불이 켜진 방만 방문하고, 스위치를 켤 때 불을 킨 방의 인접한 방에 방문한 기록이 있다면 queue에 넣습니다.

 

2. 인접한 방에 불이 켜져 있다면 방문합니다.

 

3. 마지막에 불이 켜져 있는 방의 개수를 세 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
int N, M;
vector<pair<int, int>> sw[101][101];
int arr[101][101];
int visited[101][101];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
int main()
{
    scanf("%d %d", &N, &M);
    arr[1][1] = 1;
 
    for (int i = 0; i < M; i++) {
        int x, y, a, b;
        scanf("%d %d %d %d", &x, &y, &a, &b);
        sw[y][x].emplace_back(b, a);
    }
 
    queue<pair<int, int>> q;
    q.push({ 1,1 });
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        if (visited[y][x] == 1) continue;
        visited[y][x] = 1;
 
        for (auto next : sw[y][x]) {
            if (visited[next.first][next.second] == 1) continue;
            arr[next.first][next.second] = 1;
            for (int i = 0; i < 4; i++) {
                const int yy = next.first + dy[i];
                const int xx = next.second + dx[i];
                if (yy > 0 && yy <= N && xx > 0 && xx <= N) {
                    if (visited[yy][xx] == 1) {
                        q.push({ next.first, next.second });
                        break;
                    }
                }
            }
        }
        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 && arr[yy][xx] == 1) {
                    q.push({ yy,xx });
                }
            }
        }
    }
 
    int ans = 0;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (arr[i][j] == 1) {
                ans++;
            }
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1039번 - 교환 (C++)  (0) 2022.12.01
[ 백준 ] 1669번 - 멍멍이 쓰다듬기 (C++)  (0) 2022.11.30
[ 백준 ] 2550번 - 전구 (C++)  (0) 2022.11.28
[ 백준 ] 17182번 - 우주 탐사선 (C++)  (0) 2022.11.27
[ 백준 ] 15591번 - MooTube (Silver) (C++)  (0) 2022.11.26
반응형

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

 

15591번: MooTube (Silver)

농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각각의 노드 간 관계를 입력받을 때 쌍방향 그래프로 저장합니다.

 

2. k와 v를 입력 받으면 bfs를 통해 유사도가 k 이상인 값들을 queue에 넣고, k보다 작다면 queue에 넣지 않습니다.

 

3. 유사도가 k 이상이라면 ret++를 해주고 bfs가 끝날 때 ret를 return 해줍니다.

 

4. return 된 값을 출력해줍니다.

 

[ 소스코드 ]

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<vector>
#include<cstring>
 
using namespace std;
 
int N, Q;
vector<pair<int,int>> list[5001];
int visited[5001];
 
 
int bfs(int k, int v)
{
    queue<pair<int, int>> q;
    q.push({ v,987654321 });
    memset(visited, 0, 4*(N+1));
 
    int ret = 0;
    visited[v] = 1;
 
    while (!q.empty()) {
        const int cur = q.front().first;
        const int usado = q.front().second;
        q.pop();
 
        for (auto next : list[cur]) {
            const int temp = min(usado, next.second);
 
            if (visited[next.first] != 1) {
                visited[next.first] = 1;
                if (temp >= k) {
                    ret++;
                }
                else{    //유사도가 k보다 작은 값이 하나라도 있다면 이후 모두 낮기 때문에
                    continue;
                }
 
                q.push({ next.first, temp });
            }
        }
    }
 
    return ret;
}
 
int main()
{
    scanf("%d %d", &N, &Q);
 
    for (int i = 0; i < N-1; i++) {
        int p, q, r;
        scanf("%d %d %d", &p, &q, &r);
        list[p].emplace_back(q, r);
        list[q].emplace_back(p, r);
    }
 
    for (int i = 0; i < Q; i++) {
        int k, v;
        scanf("%d %d", &k, &v);
 
        printf("%d\n", bfs(k, v));
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2550번 - 전구 (C++)  (0) 2022.11.28
[ 백준 ] 17182번 - 우주 탐사선 (C++)  (0) 2022.11.27
[ 백준 ] 4991번 - 로봇 청소기 (C++)  (0) 2022.11.25
[ 백준 ] 6087번 - 레이저 통신 (C++)  (0) 2022.11.24
[ 백준 ] 4485번 - 녹색 옷 입은 애가 젤다지? (C++)  (0) 2022.11.23
반응형

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

 

4991번: 로봇 청소기

각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 먼지 간의 거리를 저장할 dist [ i ][ j ] 배열을 만듭니다.

 

2. dist 배열을 만들어 먼지의 위치를 저장합니다.

 

3. dfs를 통해 각 지점까지 이동하는 모든 경우의 수를 뽑고, 마지막에 이동 거리 중 가장 적은 값을 ans에 저장합니다.

 

4. ans를 출력하고, 만약 이동할 수 없는 곳이 있다면 -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
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
 
using namespace std;
 
int w, h;
char arr[21][21];
int visited[10];
int dist[10][10];    //i부터 j까지 거리
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int ans;
vector<pair<int, int>> dirt;
 
struct pos {
    int y;
    int x;
    int cnt;
};
 
int bfs(int from, int to)    //시작점부터 도착점까지 거리
{
    queue<pos> q;
    int visited[21][21] = { 0 };
 
    q.push({ dirt[from].first,dirt[from].second,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 (y == dirt[to].first && x == dirt[to].second) {
            return cnt;
        }
 
        if (visited[y][x] == 1) continue;
        visited[y][x] = 1;
 
        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 (visited[yy][xx] != 1 && arr[yy][xx] != 'x') {
                    q.push({ yy,xx,cnt + 1 });
                }
            }
        }
    }
 
    return -1;
}
 
void dfs(int level, int cur, int hap)    //cur부터 i까지 거리를 hap에 저장
{
    if (ans == -1) return;
 
    if (level == dirt.size() - 1) {
        ans = min(ans, hap);
        return;
    }
 
    for (int i = 1; i < dirt.size(); i++) {
        if (visited[i] != 1) {
            visited[i] = 1;
            if (dist[cur][i] == -1) {
                dist[cur][i] = bfs(cur, i);
            }
            dist[i][cur] = dist[cur][i];
            if (dist[cur][i] == -1) {
                ans = -1;
                return;
            }
            hap += dist[cur][i];
            dfs(level + 1, i, hap);
            hap -= dist[cur][i];
            visited[i] = 0;
        }
    }
}
 
int main()
{
    while (1) {
        scanf("%d %d", &w, &h);
 
        if (w == 0 && h == 0) break;
 
        dirt.clear();
        dirt.emplace_back(0, 0);
        ans = 987654321;
        memset(dist, -1, sizeof(dist));
 
        for (int i = 0; i < 10; i++) {
            visited[i] = 0;
        }
 
        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] == 'o') {
                    dirt[0].first = i;
                    dirt[0].second = j;
                }
                if (arr[i][j] == '*') {
                    dirt.emplace_back(i, j);
                }
            }
        }
 
        dfs(0, 0, 0);
 
        printf("%d\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17182번 - 우주 탐사선 (C++)  (0) 2022.11.27
[ 백준 ] 15591번 - MooTube (Silver) (C++)  (0) 2022.11.26
[ 백준 ] 6087번 - 레이저 통신 (C++)  (0) 2022.11.24
[ 백준 ] 4485번 - 녹색 옷 입은 애가 젤다지? (C++)  (0) 2022.11.23
[ 백준 ] 2151번 - 거울 설치 (C++)  (0) 2022.11.22

+ Recent posts

티스토리툴바