반응형

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

 

18405번: 경쟁적 전염

첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. priority_queue를 만들어서 바이러스의 번호의 오름차순으로 좌표를 넣습니다.

 

2. bfs를 통해 시험관을 채워주고, 만약 입력받은 좌표에 바이러스가 생기면 그 바이러스 번호를 출력하고 프로그램을 종료합니다.

 

3. 시간이 다 지날 때까지 바이러스가 존재하지 않는다면 0을 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, K;
int arr[201][201];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
 
struct node {
    int x;
    int y;
    int cnt;
};
 
struct cmp {
    bool operator()(node right, node left) {
        if (left.cnt == right.cnt) return arr[left.x][left.y] < arr[right.x][right.y];
        return left.cnt < right.cnt;
    }
};
 
int main()
{
    scanf("%d %d", &N, &K);
    priority_queue<node, vector<node>, cmp> pq;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] != 0) {
                pq.push({ i,j,0 });
            }
        }
    }
 
    int S, X, Y;
    scanf("%d %d %d", &S, &X, &Y);
    
    while(!pq.empty()) {
        const int x = pq.top().x;
        const int y = pq.top().y;
        const int cnt = pq.top().cnt;
        pq.pop();
 
        if (arr[X][Y] != 0) {
            printf("%d", arr[X][Y]);
            return 0;
        }
 
        if (cnt == S) continue;
 
        for (int i = 0; i < 4; i++) {
            const int xx = x + dx[i];
            const int yy = y + dy[i];
 
            if (xx > 0 && xx <= N && yy > 0 && yy <= N) {
                if (arr[xx][yy] == 0) {
                    arr[xx][yy] = arr[x][y];
                    pq.push({ xx,yy,cnt + 1 });
                }
            }
        }
    }
 
    printf("%d", arr[X][Y]);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2617번 - 구슬 찾기 (C++)  (0) 2023.02.27
[ 백준 ] 18235번 - 지금 만나러 갑니다 (C++)  (0) 2023.02.26
[ 백준 ] 1613번 - 역사 (C++)  (0) 2023.02.24
[ 백준 ] 1162번 - 도로포장 (C++)  (0) 2023.02.23
[ 백준 ] 6497번 - 전력난 (C++)  (0) 2023.02.22
반응형

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

 

1944번: 복제 로봇

첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 미로를 입력받고, S와 K의 좌표에 번호를 붙입니다.

 

2. 2중 for문을 이용하여 S와 K의 모든 좌표들끼리 연결하고, edge 배열에 시작점과 도착점, 거리를 저장합니다.

 

3. edge 배열을 거리를 기준으로 오름차순으로 정렬합니다.

 

4. Union-Find를 이용하여 모든 노드를 연결하고, ans에 거리를 더합니다.

 

5. 위의 과정에서 노드를 연결할 때마다 cnt++ 해줍니다.

 

6. cnt == M일 경우 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
123
124
125
126
127
128
129
130
131
132
133
134
#include<iostream>
#include<algorithm>
#include<queue>
 
using namespace std;
 
struct node {
    int u;
    int v;
    int d;
};
 
bool cmp(node left, node right)
{
    return left.d < right.d;
}
 
int N, M;
char arr[51][51];
int check[251][251];
int key[51][51];
vector<node> edge;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int vect[251];
 
void getEdge(int y, int x)
{
    int u = key[y][x];
    int visited[50][50] = { 0 };
    queue<node> q;
    q.push({ y,x,0 });
    visited[y][x] = 1;
 
    while (!q.empty()) {
        const int y = q.front().u;
        const int x = q.front().v;
        const int cnt = q.front().d;
        q.pop();
 
        if ((arr[y][x] == 'S' || arr[y][x] == 'K') && cnt != 0) {
            int v = key[y][x];
            if (check[u][v] != 1 && check[v][u] != 1) {
                edge.push_back({ u,v,cnt });
                check[u][v] = 1;
                check[v][u] = 1;
            }
        }
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy > 0 && yy < N - 1 && xx>0 && xx < N - 1) {
                if (arr[yy][xx] != '1' && visited[yy][xx] != 1) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx,cnt + 1 });
                }
            }
        }
    }
}
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++) {
        scanf("%s", arr[i]);
    }
 
    for (int i = 1; i <= M; i++) {
        vect[i] = i;
    }
 
    int cnt = 1;
 
    for (int i = 1; i < N - 1; i++) {
        for (int j = 1; j < N - 1; j++) {
            if (arr[i][j] == 'S') {
                key[i][j] = 0;
            }
            else if(arr[i][j] == 'K'){
                key[i][j] = cnt++;
            }
        }
    }
 
    for (int i = 1; i < N - 1; i++) {
        for (int j = 1; j < N - 1; j++) {
            if (arr[i][j] == 'S' || arr[i][j] == 'K') {
                getEdge(i, j);
            }
        }
    }
 
    sort(edge.begin(), edge.end(), cmp);
 
    int ans = 0;
    cnt = 0;
 
    for (auto& next : edge) {
        const int u = next.u;
        const int v = next.v;
        const int d = next.d;
 
        if (Find(u) != Find(v)) {
            Union(u, v);
            ans += d;
            cnt++;
        }
    }
 
    if (cnt == M) {
        printf("%d", ans);
        return 0;
    }
 
    printf("-1");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2406번 - 안정적인 네트워크 (C++)  (0) 2023.02.19
[ 백준 ] 20010번 - 악덕 영주 혜유 (C++)  (0) 2023.02.18
[ 백준 ] 14621번 - 나만 안되는 연애 (C++)  (0) 2023.02.16
[ 백준 ] 1937번 - 욕심쟁이 판다 (C++)  (0) 2023.02.15
[ 백준 ] 7570번 - 줄 세우기 (C++)  (0) 2023.02.14
반응형

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

 

17836번: 공주님을 구해라!

용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited [ y ][ x ][ gram ] 배열을 만들어 방문을 기록해 줍니다.

 

2. bfs를 이용하여 (1, 1)에서 (N, M)까지 이동합니다.

 

3. 이동할 때까지 걸린 시간이 T를 넘지 않으면 시간을 출력하고, 그렇지 않으면 Fail을 출력합니다.

 

[ 소스코드 ]

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, T;
int arr[101][101];
int visited[101][101][2];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
struct node {
    int y;
    int x;
    int cnt;
    int gram;
};
 
int main()
{
    scanf("%d %d %d", &N, &M, &T);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    queue<node> q;
    q.push({ 1,1,0,false });
    visited[1][1][0] = 1;
 
    while (!q.empty()) {
        const int y = q.front().y;
        const int x = q.front().x;
        const int cnt = q.front().cnt;
        const int gram = q.front().gram;
        q.pop();
 
        if (cnt > T) continue;
 
        if (y == N && x == M) {
            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] == 1 && gram == true) || arr[yy][xx] == 0) {
                    if (visited[yy][xx][gram] != 1) {
                        visited[yy][xx][gram] = 1;
                        q.push({ yy,xx,cnt + 1,gram });
                    }
                }
                else if (arr[yy][xx] == 2) {
                    if (visited[yy][xx][1] != 1) {
                        visited[yy][xx][1] = 1;
                        q.push({ yy,xx,cnt + 1,1 });
                    }
                }
 
            }
        }
    }
 
    printf("Fail");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11085번 - 군사 이동 (C++)  (0) 2023.02.13
[ 백준 ] 2565번 - 전깃줄 (C++)  (0) 2023.02.12
[ 백준 ] 15971번 - 두 로봇 (C++)  (0) 2023.02.10
[ 백준 ] 2637번 - 장난감 조립 (C++)  (0) 2023.02.09
[ 백준 ] 11658번 - 구간 합 구하기 3 (C++)  (0) 2023.02.08
반응형

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

 

15971번: 두 로봇

입력에서 두 번째 줄에 주어지는 방번호는 1과 2, 세 번째 줄에 주어지는 방 번호는 2와 3, …, i번째 줄에 주어지는 방 번호는 i-1과 i, …, N번째 줄에 주어지는 방 번호는 N-1과 N이다 (아래 입력과

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited 배열을 만들어 방문을 기록해 줍니다.

 

2. 그래프를 입력받고, bfs를 이용하여 시작점부터 끝점까지 이동 거리를 구해줍니다.

 

3. 위의 과정에서 지나갔던 통로 중 가장 긴 통로를 이동 거리에서 빼줍니다.

 

4. 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
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
struct node {
    int cur;
    int cost;
    int max;
};
 
int N, s, e;
vector<pair<int, int>> list[100001];
int visited[100001];
 
int main()
{
    scanf("%d %d %d", &N, &s, &e);
 
    for (int i = 0; i < N - 1; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        list[a].push_back({ b,c });
        list[b].push_back({ a,c });
    }
 
    queue<node> q;
    q.push({ s,0,0 });
    visited[s] = 1;
 
    while (!q.empty()) {
        const int cur = q.front().cur;
        const int cost = q.front().cost;
        const int Max = q.front().max;
        q.pop();
 
        if (cur == e) {
            printf("%d", cost - Max);
            return 0;
        }
 
        for (auto& next : list[cur]) {
            if (visited[next.first] != 1) {
                visited[next.first] = 1;
                q.push({ next.first, cost + next.second, max(Max, next.second) });
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2565번 - 전깃줄 (C++)  (0) 2023.02.12
[ 백준 ] 17836번 - 공주님을 구해라! (C++)  (0) 2023.02.11
[ 백준 ] 2637번 - 장난감 조립 (C++)  (0) 2023.02.09
[ 백준 ] 11658번 - 구간 합 구하기 3 (C++)  (0) 2023.02.08
[ 백준 ] 2458번 - 키 순서 (C++)  (0) 2023.02.07
반응형

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

 

2211번: 네트워크 복구

첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다

www.acmicpc.net

 

 

[ 문제풀이 ]

1. visited 배열을 만들고 visited [ i ] = 987654321로 초기화해 줍니다.

 

2. node struct를 만들어서 연결된 각각의 컴퓨 번호와 비용을 저장합니다.

 

3. dijkstra를 이용하여 네트워크를 복구하고, 네트워크가 연결될 때마다 ans에 각각의 컴퓨터 번호를 push 해줍니다.

 

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
#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
int N, M;
vector<pair<int, int>> list[1001];
int visited[1001];
vector<pair<int,int>> ans;
 
struct node {
    int before;
    int cur;
    int cost;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.cost < right.cost;
    }
};
 
int main()
{
    priority_queue<node, vector<node>, cmp> pq;
    scanf("%d %d", &N, &M);
 
    fill(visited, visited + N + 1, 987654321);
    visited[1] = 0;
 
    for (int i = 0; i < M; i++) {
        int A, B, C;
        scanf("%d %d %d", &A, &B, &C);
        list[A].push_back({ B,C });
        list[B].push_back({ A,C });
    }
 
    pq.push({ 0,1,0 });
 
    while (!pq.empty()) {
        const int before = pq.top().before;
        const int cur = pq.top().cur;
        const int cost = pq.top().cost;
        pq.pop();
 
        if (visited[cur] < cost) continue;
 
        ans.push_back({ before,cur });
 
        for (auto& next : list[cur]) {
            if (visited[next.first] > cost + next.second) {
                visited[next.first] = cost + next.second;
                pq.push({ cur, next.first, cost + next.second });
            }
        }
    }
 
    printf("%d\n", ans.size() - 1);
 
    for (int i = 1; i < ans.size(); i++) {
        printf("%d %d\n", ans[i].first, ans[i].second);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11658번 - 구간 합 구하기 3 (C++)  (0) 2023.02.08
[ 백준 ] 2458번 - 키 순서 (C++)  (0) 2023.02.07
[ 백준 ] 17835번 - 면접보는 승범이네 (C++)  (0) 2023.02.05
[ 백준 ] 1368번 - 물대기 (C++)  (0) 2023.02.04
[ 백준 ] 1261번 - 알고스팟 (C++)  (0) 2023.02.03
반응형

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

 

5214번: 환승

첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited [ N + K ] 배열을 만들어서 방문 여부를 저장합니다.

 

2. 하이퍼링크를 정점으로 두고, 하이퍼링크를 입력받을 때 다음과 같이 간선을 설정해 줍니다.

list [ N + i ].push_back(station)

list [station].push_back(N + i)

 

3. 즉, 역과 연결된 정점은 하이퍼링크이고, 하이퍼링크와 연결된 정점은 역으로 설정해 줍니다.

 

4. 만약 현재 정점이 N보다 크다면 역이 아니고 하이퍼링크이므로, 현재 방문한 역의 개수를 queue에 넣어주고, N보다 작거나 같다면 역에 방문한 것이므로, 현재 방문한 역의 개수에 +1을 해주어 queue에 넣어줍니다.

 

5. 현재 역이 N번 역이라면 cnt를 출력해 줍니다.

 

6. 방문할 수 없다면 -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
#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
int N, K, M;
vector<int> list[101001];
int visited[101001];
 
struct node {
    int cur;
    int cnt;
};
 
int main()
{
    scanf("%d %d %d", &N, &K, &M);
 
    for (int i = 1; i <= M; i++) {
        for (int j = 0; j < K; j++) {
            int station;
            scanf("%d", &station);
            list[station].push_back(N + i);
            list[N + i].push_back(station);
        }
    }
 
    queue<node> q;
    q.push({ 1,1 });
    visited[1] = 1;
 
    while (!q.empty()) {
        const int cur = q.front().cur;
        const int cnt = q.front().cnt;
        q.pop();
 
        if (cur == N) {
            printf("%d", cnt);
            return 0;
        }
 
        for (auto next : list[cur]) {
            if (visited[next] != 1) {
                visited[next] = 1;
                if (next > N) {
                    q.push({ next, cnt });
                }
                else {
                    q.push({ next,cnt + 1 });
                }
            }
        }
    }
 
    printf("-1");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1261번 - 알고스팟 (C++)  (0) 2023.02.03
[ 백준 ] 10423번 - 전기가 부족 (C++)  (0) 2023.02.02
[ 백준 ] 1584번 - 게임 (C++)  (0) 2023.01.31
[ 백준 ] 1175번 - 배달 (C++)  (0) 2023.01.30
[ 백준 ] 13418번 - 학교 탐방하기 (C++)  (0) 2023.01.29
반응형

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

 

1175번: 배달

어제 선물을 모두 포장한 민식이는 이제 선물을 배달하려고 한다. 민식이가 선물을 배달할 곳은 이 문제를 읽는 사람들이 앉아 있는 교실이다. 교실은 직사각형모양이고, 모두 같은 크기의 정사

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited [ N ][ M ][ dir ][ del ] 배열을 만들어서 위치, 방향, 배달 여부를 저장합니다.

 

2. 지도에서 S의 위치를 queue에 넣고, '.'로 초기화합니다.

 

3. 지도에서 C의 위치를 '0', '1'로 초기화합니다.

 

4. bfs를 통해 배달을 하고, 숫자를 만나면 del | (1 << arr [ yy ][ xx ] - '0')를 통해 배달 여부를 초기화합니다.

 

5. 배달을 완료했을 때 cnt를 출력합니다.

 

6. 배달이 불가능할 때 -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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int visited[50][50][4][4];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
char arr[51][51];
 
struct node {
    int y;
    int x;
    int dir;
    int del;
    int cnt;
};
 
int main()
{
    scanf("%d %d", &N, &M);
    queue<node> q;
 
    for (int i = 0; i < N; i++) {
        scanf("%s", &arr[i]);
    }
 
    int cnt = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == 'S') {
                q.push({ i,j,-1,0,0 });
                visited[i][j][0][0] = 1;
                visited[i][j][1][0] = 1;
                visited[i][j][2][0] = 1;
                visited[i][j][3][0] = 1;
                arr[i][j] = '.';
            }
            if (arr[i][j] == 'C') {
                arr[i][j] = '0' + cnt++;
            }
        }
    }
 
    while (!q.empty()) {
        const int y = q.front().y;
        const int x = q.front().x;
        const int dir = q.front().dir;
        const int del = q.front().del;
        const int cnt = q.front().cnt;
        q.pop();
 
        if (del == 3) {
            printf("%d", cnt);
            return 0;
        }
 
        for (int i = 0; i < 4; i++) {
            if (i != dir) {
                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] == '.' && visited[yy][xx][i][del] == 0) {
                        visited[yy][xx][i][del] = 1;
                        q.push({ yy,xx,i,del,cnt + 1 });
                    }
                    else if (arr[yy][xx] >= '0' && arr[yy][xx] < '2') {
                        const int temp = del | (1 << arr[yy][xx] - '0');
                        if (visited[yy][xx][i][temp] == 0) {
                            visited[yy][xx][i][temp] = 1;
                            q.push({ yy,xx,i,temp,cnt + 1});
                        }
                    }
                }
            }
        }
    }
 
    printf("-1");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 5214번 - 환승 (C++)  (0) 2023.02.01
[ 백준 ] 1584번 - 게임 (C++)  (0) 2023.01.31
[ 백준 ] 13418번 - 학교 탐방하기 (C++)  (0) 2023.01.29
[ 백준 ] 16398번 - 행성 연결 (C++)  (0) 2023.01.28
[ 백준 ] 17090번 - 미로 탈출하기 (C++)  (0) 2023.01.27
반응형

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

 

14923번: 미로 탈출

홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited [ 1001 ][ 1001 ][ 2 ] 배열을 만들어서 벽을 부순 여부와 방문 여부를 기록합니다.

 

2. bfs를 활용하여 벽을 부순 횟수와 움직인 횟수 등을 queue에 넣고, 현재 위치가 Ex, Ey라면 cnt를 출력합니다.

 

3. 도착할 수 없는 경우 -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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int Hx, Hy;
int Ex, Ey;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int arr[1001][1001];
int visited[1001][1001][2];
 
struct pos {
    int x;
    int y;
    int wall;
    int cnt;
};
 
int main()
{
    scanf("%d %d", &N, &M);
    scanf("%d %d", &Hx, &Hy);
    scanf("%d %d", &Ex, &Ey);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    queue<pos> q;
 
    q.push({ Hx,Hy,0,0 });
    visited[Hx][Hy][0] = 1;
 
    while (!q.empty()) {
        const int y = q.front().y;
        const int x = q.front().x;
        const int wall = q.front().wall;
        const int cnt = q.front().cnt;
        q.pop();
 
        if (y == Ey && x == Ex) {
            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 (xx > 0 && xx <= N && yy > 0 && yy <= M) {
                if (wall == 0 && arr[xx][yy] == 1) {
                    if (visited[xx][yy][1] != 1) {
                        visited[xx][yy][1] = 1;
                        q.push({ xx,yy,1,cnt + 1 });
                    }
                }
                if (arr[xx][yy] == 0) {
                    if (visited[xx][yy][wall] != 1) {
                        visited[xx][yy][wall] = 1;
                        q.push({ xx,yy,wall,cnt + 1 });
                    }
                }
            }
        }
    }
 
    printf("-1");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 16398번 - 행성 연결 (C++)  (0) 2023.01.28
[ 백준 ] 17090번 - 미로 탈출하기 (C++)  (0) 2023.01.27
[ 백준 ] 5558번 - チーズ (Cheese) (C++)  (0) 2023.01.25
[ 백준 ] 3770번 - 대한민국 (C++)  (0) 2023.01.24
[ 백준 ] 9463번 - 순열 그래프 (C++)  (0) 2023.01.23
반응형

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

 

5558번: チーズ (Cheese)

入力は H+1 行ある．1 行目には 3 つの整数 H，W，N (1 ≦ H ≦ 1000，1 ≦ W ≦ 1000，1 ≦ N ≦ 9) がこの順に空白で区切られて書かれている．2 行目から H+1 行目までの各行には，'S'，'1', '2', ..., '9'，

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 지도를 입력받고, S의 위치를 queue에 넣습니다.

 

2. visited [ 1001 ][ 1001 ][ 10 ] 배열을 만들어 먹은 치즈와 방문 여부를 저장합니다.

 

3. bfs를 이용하여 먹은 치즈가 K일 경우 현재까지 이동한 거리인 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
#include<iostream>
#include<queue>
 
using namespace std;
 
int H, W, N;
char arr[1001][1001];
int visited[1001][1001][10];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
struct pos {
    int y;
    int x;
    int cheese;
    int cnt;
};
 
int main()
{
    queue<pos> q;
    scanf("%d %d %d", &H, &W, &N);
 
    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] == 'S') {
                q.push({ i,j,0,0 });
                visited[i][j][0] = 1;
                break;
            }
        }
        if (!q.empty()) break;
    }
 
    while (!q.empty()) {
        const int y = q.front().y;
        const int x = q.front().x;
        const int cheese = q.front().cheese;
        const int cnt = q.front().cnt;
        q.pop();
 
        if (cheese == N) {
            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] != 'X') {
                    if (arr[yy][xx] == cheese + '0' + 1) {
                        if (visited[yy][xx][cheese + 1] != 1) {
                            visited[yy][xx][cheese + 1] = 1;
                            q.push({ yy,xx,cheese + 1,cnt + 1 });
                        }
                    }
                    else {
                        if (visited[yy][xx][cheese] != 1) {
                            visited[yy][xx][cheese] = 1;
                            q.push({ yy,xx,cheese,cnt + 1 });
                        }
                    }
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17090번 - 미로 탈출하기 (C++)  (0) 2023.01.27
[ 백준 ] 14923번 - 미로 탈출 (C++)  (0) 2023.01.26
[ 백준 ] 3770번 - 대한민국 (C++)  (0) 2023.01.24
[ 백준 ] 9463번 - 순열 그래프 (C++)  (0) 2023.01.23
[ 백준 ] 10090번 - Counting Inversions (C++)  (0) 2023.01.22
반응형

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

 

14226번: 이모티콘

영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. S를 입력받고, visited[ cur ][ copy ] 배열을 통해 현재 수와 클립보드에 저장된 수의 방문 여부를 체크합니다.

 

2. 다음의 세 경우를 queue에 넣어줍니다.

  - 복사 q.push({ cur, cur, cnt + 1 })

  - 붙여넣기 q.push({ cur + copy, copy, cnt + 1 })

  - 지우기 q.push({ cur - 1, copy, cnt + 1 })

 

3. S와 cur이 일치하면 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
#include<iostream>
#include<queue>
 
using namespace std;
 
int S;
int visited[2001][2001];
 
struct node {
    int cur;
    int copy;
    int cnt;
};
 
int main()
{
    scanf("%d", &S);
 
    queue<node> q;
 
    q.push({ 1,0,0 });
 
    while (!q.empty()) {
        const int cur = q.front().cur;
        const int copy = q.front().copy;
        const int cnt = q.front().cnt;
        q.pop();
 
        if(cur > 2000) continue;
        if (visited[cur][copy] == 1) continue;
        visited[cur][copy] = 1;
 
        if (S == cur) {
            printf("%d", cnt);
            return 0;
        }
 
        q.push({ cur,cur,cnt + 1 });
        q.push({ cur + copy,copy,cnt + 1 });
        if (cur - 1 > 0) {
            q.push({ cur - 1,copy,cnt + 1 });
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 16118번 - 달빛 여우 (C++)  (0) 2023.01.10
[ 백준 ] 16562번 - 친구비 (C++)  (0) 2023.01.09
[ 백준 ] 2470번 - 두 용액 (C++)  (0) 2023.01.07
[ 백준 ] 17141번 - 연구소 2 (C++)  (0) 2023.01.06
[ 백준 ] 1275번 - 커피숍2 (C++)  (0) 2023.01.05

+ Recent posts

티스토리툴바