반응형

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

 

11404번: 플로이드

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽어보고 오시는 걸 추천드립니다!!

https://rudalsd.tistory.com/24?category=1064608 

 

플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

오늘 설명할 알고리즘은 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 플로이드 와샬 알고리즘이

rudalsd.tistory.com

 

이번 문제에서는 각 노드까지의 최단거리를 출력하지만 갈 수 없는 곳은 0으로 출력해야 한다는 조건이 있었습니다.

 

따라서 한번도 초기화되지 않았던 노드는 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
#include <iostream>
 
using namespace std;
 
int n, m;
long long cost[101][101];
 
int main()
{
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++) {            //출발지와 도착지가 같을 때 0으로 초기화
        for (int j = 1; j <= n; j++) {        //아니라면 INF로 초기화
            if (i == j) {
                cost[i][j] = 0;
            }
            else {
                cost[i][j] = 99999999999;
            }
        }
    }
 
    for (int i = 0; i < m; i++) {            //출발지와 도착지가 같은 간선이 여러개일 때
        int a, b, c;                        //가장 짧은 거리로 초기화
        scanf("%d %d %d", &a, &b, &c);
        if (cost[a][b] > c) {
            cost[a][b] = c;
        }
    }
 
    for (int k = 1; k <= n; k++) {            //거쳐가는 노드
        for (int i = 1; i <= n; i++) {        //출발 노드
            for (int j = 1; j <= n; j++) {    //도착 노드
                if (cost[i][j] > cost[i][k] + cost[k][j]) {
                    cost[i][j] = cost[i][k] + cost[k][j];
                }
            }
        }
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (cost[i][j] == 99999999999) {    //한번도 갱신이 되지 않았다면
                cout << 0 << " ";                //갈 수 없으므로 0출력
            }
            else {
                cout << cost[i][j] << " ";
            }
        }
        cout << endl;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2638번 - 치즈 (C++)  (0) 2022.06.13
[ 백준 ] 13460번 - 구슬 탈출 2 (C++)  (0) 2022.06.12
[ 백준 ] 1865번 - 웜홀 (C++)  (0) 2022.06.10
[ 백준 ] 1238번 - 파티 (C++)  (0) 2022.06.09
[ 백준 ] 12865번 - 평범한 배낭 (C++)  (0) 2022.06.08
반응형

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

 

1865번: 웜홀

첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500),

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽어보고 오시는 걸 추천드립니다!!

https://rudalsd.tistory.com/22

 

벨만 포드 알고리즘(Bellman-Ford Algorithm)

오늘 설명할 알고리즘은 벨만 포드 알고리즘(Bellman-Ford Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 벨만 포드 알고리즘이 dijkstra보다 시

rudalsd.tistory.com

 

이번 문제에서는 일반적인 최단거리를 구하는 문제들과는 다르게 단순히 음의 cycle이 있는지 없는지만 체크해주면 되는 문제입니다.

 

따라서 일반적인 벨만 포드 알고리즘과 달리 각 노드까지의 거리를 어떤 수로도 초기화시켜주어도 되고, 갱신이 된 적이 없는 노드들도 모두 돌아가면서 거리가 갱신되는지 체크해주면 됩니다.

 

마지막에 거리가 갱신이 된다면 음의 사이클이 존재한다는 뜻이므로 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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<vector>
#include<cstring>
 
using namespace std;
 
int N, M, W;
 
struct Node {
    int to;
    int dist;
};
 
int dist[501];
 
int main()
{
    int T;
    cin >> T;
 
    for (int t = 0; t < T; t++) {
        cin >> N >> M >> W;
        vector<Node> list[501];
 
        memset(dist, -1, sizeof(dist));
 
        for (int i = 0; i < M; i++) {
            int S, E, T;
            scanf("%d %d %d", &S, &E, &T);
            list[S].push_back({ E,T });
            list[E].push_back({ S,T });
        }
 
        for (int i = 0; i < W; i++) {
            int S, E, T;
            scanf("%d %d %d", &S, &E, &T);
            list[S].push_back({ E,-T });
        }
 
        int flag = 0;
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                for (int k = 0; k < list[j].size(); k++) {
                    int next = list[j][k].to;
                    int nextDist = list[j][k].dist;
                    if (dist[next] > nextDist + dist[j]) {    //N번째에도 거리가 줄어들었다면 음의 cycle이 있다는 뜻이므로
                        dist[next] = nextDist + dist[j];
                        if (i == N) {
                            flag = 1;
                        }
                    }
                }
            }
        }
 
        if (flag == 1) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 13460번 - 구슬 탈출 2 (C++)  (0) 2022.06.12
[ 백준 ] 11404번 - 플로이드 (C++)  (0) 2022.06.11
[ 백준 ] 1238번 - 파티 (C++)  (0) 2022.06.09
[ 백준 ] 12865번 - 평범한 배낭 (C++)  (0) 2022.06.08
[ 백준 ] 9663번 - N-Queen (C++)  (0) 2022.06.07
반응형

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

 

1238번: 파티

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어

www.acmicpc.net

 

 

[ 문제풀이 ]

 

총 두 번의 dijkstra로 정답을 쉽게 구할 수 있는 문제였습니다.

 

먼저 정방향으로 간선들을 모두 저장해주고 이를 이용해서 dijkstra를 돌리면 특정 정점에서 각 정점까지의 최단거리를 구할 수 있습니다.

 

하지만 왕복을 해야 하기 때문에 역방향 간선들을 이용하여 dijkstra를 한번 더 돌려줍니다. 그렇게 되면 각 정점에서 특정 정점까지 오는데 걸리는 최단 거리를 구할 수 있습니다.

 

그리고 각 정점까지 가는 데 이동한 거리를 더해주고 그중 가장 큰 값을 출력하면 되는 문제입니다.

 

[ 소스 코드 ]

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;
 
struct Node {
    int to;
    int cost;
};
 
struct cmp {
    bool operator()(Node right, Node left)
    {
        return left.cost < right.cost;
    }
};
 
int N, M, X;
vector<Node> list[1001];        //간선들을 정방향으로 저장할 vector list
vector<Node> relist[1001];        //간선들을 역방향으로 저장할 vector relist
int dist[1001];
 
void dijkstra(vector<Node> list[])        //한 점에서 출발하여 각 노드까지 거리를 dist 배열에 저장
{
    int visited[1001] = { 0 };
    priority_queue<Node, vector<Node>, cmp> pq;
    pq.push({ X, 0 });
 
    while (!pq.empty())
    {
        int node = pq.top().to;
        int cost = pq.top().cost;
        pq.pop();
 
        if (visited[node]) continue;
        visited[node]++;
        dist[node] += cost;
 
        for (int i = 0; i < list[node].size(); i++) {
            int next = list[node][i].to;
            int nextCost = list[node][i].cost;
            if (visited[next] != 1) {
                pq.push({ next, cost + nextCost });
            }
        }
    }
}
 
int main()
{
    cin >> N >> M >> X;
 
    for (int i = 0; i < M; i++) {
        int A, B, T;
        scanf("%d %d %d", &A, &B, &T);
        list[A].push_back({ B,T });        //간선을 정방향으로 저장
        relist[B].push_back({ A,T });    //간선을 역방향으로 저장
    }
 
    int ans = 0;
 
    dijkstra(list);        //정방향 dijkstra
    dijkstra(relist);    //역방향 dijkstra
 
    for (int i = 1; i <= N; i++) {
        if (ans < dist[i]) {
            ans = dist[i];    //거리의 최댓값을 ans에 저장
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11404번 - 플로이드 (C++)  (0) 2022.06.11
[ 백준 ] 1865번 - 웜홀 (C++)  (0) 2022.06.10
[ 백준 ] 12865번 - 평범한 배낭 (C++)  (0) 2022.06.08
[ 백준 ] 9663번 - N-Queen (C++)  (0) 2022.06.07
[ 백준 ] 1504번 - 특정한 최단 경로 (C++)  (0) 2022.06.06
반응형

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

 

1504번: 특정한 최단 경로

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존

www.acmicpc.net

 

 

[ 문제풀이 ]

 

쉬운 다익스트라 문제였습니다.

 

다만 경로를 쪼개서 구해야 했고, 경우의 수가 두 가지가 있기 때문에 두 번의 계산 중 더 작은 값이 답이 되었습니다.

 

1 -> v1 -> v2 -> N

1 -> v2 -> v1 -> N

 

이 두가지 경우 중 더 거리가 짧은 경우가 답이 됩니다.

 

[ 소스 코드 ]

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 <vector>
 
using namespace std;
 
struct Node {
    int to;
    int cost;
};
 
struct cmp {
    bool operator()(Node right, Node left)
    {
        return left.cost < right.cost;
    }
};
 
int N, E;
vector<Node> list[801];
int v[2];
 
int dijkstra(int start, int end)        //시작점과 도착점의 최단거리를 return하는 dijkstra함수
{
    priority_queue<Node, vector<Node>, cmp> pq;
    pq.push({ start, 0 });
    int visited[801] = { 0 };
 
    while (!pq.empty())
    {
        int to = pq.top().to;
        int cost = pq.top().cost;
        pq.pop();
 
        if (visited[to] == 1) continue;
        visited[to] = 1;
 
        if (to == end)
        {
            return cost;
        }
 
        for (int i = 0; i < list[to].size(); i++) {
            int next = list[to][i].to;
            int nextCost = list[to][i].cost;
            if (visited[next] != 1) {
                pq.push({ next, cost + nextCost });
            }
        }
    }
 
    return -1;
}
 
int main()
{
    cin >> N >> E;
 
    for (int i = 0; i < E; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        list[a].push_back({ b,c });
        list[b].push_back({ a,c });
    }
 
    for (int i = 0; i < 2; i++) {
        cin >> v[i];
    }
 
    int a1 = dijkstra(1, v[0]);
    int b1 = dijkstra(1, v[1]);
    int mid = dijkstra(v[0], v[1]);
    int a2 = dijkstra(v[1], N);
    int b2 = dijkstra(v[0], N);
 
    int min = a1 + mid + a2;        //1 -> v[0] -> v[1] -> N
 
    if (a1 != -1 && a2 != -1 && mid != -1) {
        if (min > b1 + mid + b2) {    //1 -> v[1] -> v[0] -> N
            min = b1 + mid + b2;
        }
    }
    else {        //경로가 없다면
        cout << -1;
        return 0;
    }
 
    cout << min;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 12865번 - 평범한 배낭 (C++)  (0) 2022.06.08
[ 백준 ] 9663번 - N-Queen (C++)  (0) 2022.06.07
[ 백준 ] 11054번 - 가장 긴 바이토닉 부분 수열 (C++)  (0) 2022.06.05
[ 백준 ] 11779번 - 최소비용 구하기 2 (C++)  (0) 2022.06.04
[ 백준 ] 17070번 - 파이프 옮기기 1 (C++)  (0) 2022.06.03
반응형

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

 

11779번: 최소비용 구하기 2

첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스

www.acmicpc.net

 

 

 

[ 문제풀이 ]

 

일반적인 최소 거리를 구하는 다익스트라 문제였습니다. 하지만 거기에 경로를 출력하라는 요구사항이 있었기 때문에 조금 더 복잡했지만 몇 줄 추가만 해주면 쉽게 풀리는 문제였습니다.

 

Bus struct 안에 경로를 저장할 vector를 추가해 주었고, 이를 pq에 넣어주면 각 인자별로 경유지를 따로 저장할 수 있기 때문에 목적지에 도착했을 때 이 경유지를 따로 저장만 해주면 됩니다.

 

[ 소스 코드 ]

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 <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
struct Bus {                    //노선의 정보를 저장할 struct
    int to;
    int cost;
    vector<int> via;
};
 
int n, m;
int visited[1001];            //방문 여부 체크
vector<Bus> list[1001];        //버스 도착지와 cost를 저장할 vector list
 
bool cmp(Bus left, Bus right)    //가격이 낮은 순으로 list를 정렬
{
    return left.cost < right.cost;
}
 
struct comp {                    //가격이 낮은 순으로 priority_queue에서 빠져나옴
    bool operator()(Bus right, Bus left)
    {
        return left.cost < right.cost;
    }
};
 
int main()
{
    int start, end;
    int ans;                //총 가격 저장할 변수
    vector<int> ansVia;        //경로를 저장할 vector
    cin >> n >> m;
 
    for (int i = 0; i < m; i++) {    //노선 정보를 list에 입력
        int start, end, cost;
        scanf("%d %d %d", &start, &end, &cost);
        list[start].push_back({ end,cost });
    }
 
    cin >> start >> end;
 
    for (int i = 1; i <= n; i++) {    //가격이 낮은 순으로 정렬
        sort(list[i].begin(), list[i].end(), cmp);
    }
 
    priority_queue<Bus, vector<Bus>, comp> pq;
    vector<int> via;
    pq.push({ start,0, via});        //시작점을 pq에 넣기
    
 
    while (!pq.empty())
    {
        int to = pq.top().to;
        int cost = pq.top().cost;
        vector<int> via = pq.top().via;
 
        pq.pop();
 
        if (visited[to] == 1) continue;    //방문했다면 continue
        visited[to]++;
        via.push_back(to);
 
        if (to == end) {        //목적지에 도착하면 비용과 경로를 저장
            ans = cost;
            ansVia = via;
            break;
        }
 
        for (int i = 0; i < list[to].size(); i++) {
            int next = list[to][i].to;
            int nextCost = list[to][i].cost;
            if (visited[next] != 1) {        //방문하지 않았다면
                pq.push({ next, cost + nextCost, via});    //다음 노드와 여기까지 오는데 드는 비용, 경로를 pq에 넣기
            }
        }
    }
 
    printf("%d\n%d\n", ans, ansVia.size());        //출력
    for (int i = 0; i < ansVia.size(); i++) {
        printf("%d ", ansVia[i]);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1504번 - 특정한 최단 경로 (C++)  (0) 2022.06.06
[ 백준 ] 11054번 - 가장 긴 바이토닉 부분 수열 (C++)  (0) 2022.06.05
[ 백준 ] 17070번 - 파이프 옮기기 1 (C++)  (0) 2022.06.03
[ 백준 ] 9251번 - LCS (C++)  (0) 2022.06.02
[ 백준 ] 15686번 - 치킨 배달 (C++)  (0) 2022.06.01
반응형

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

 

17070번: 파이프 옮기기 1

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제는 여러 가지 방법으로 풀 수 있습니다. dfs를 이용하여 모든 경우의 수를 다 구할 수도 있고, dp를 이용해서 더 빠르게 풀 수도 있습니다.

 

그중 dp를 이용한 방법에 대해서 설명드리겠습니다. 어떤 한 좌표에 파이프가 올 수 있는 경우의 수를 dp [ state ][ y ][ x ] 배열에 각각 저장하면서 마지막에 dp [ 0 ][ N ][ N ] + dp [ 1 ][ N ][ N ] + dp [ 2 ][ N ][ N ]을 출력하면 됩니다. 

 

먼저 한 점 y, x에 올 수 있는 파이프의 개수를 저장하기 위해서는 각각의 상황에 따라 다르게 구해주어야합니다.

 

예를 들어 0번 상태(가로) 일 때는 1번 상태(세로)의 파이프는 올 수 없습니다. 따라서, dp [ 0 ][ y ][ x ] = dp[ 0 ][ y ][ x - 1 ] + dp[ 2 ][ y ][ x - 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
#include <iostream>
 
using namespace std;
 
int N;
int arr[17][17];
int dp[3][17][17];            //각 상태를 저장할 dp배열 [state][y][x] state 0:가로 1:세로 2:대각
 
int main()
{
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> arr[i][j];
        }
    }
 
    dp[0][1][2] = 1;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (arr[i][j] != 1) {        //파이프가 움직일 수 있을 때만
                dp[0][i][j] += dp[0][i][j - 1] + dp[2][i][j - 1];    //가로, 대각
                dp[1][i][j] += dp[1][i - 1][j] + dp[2][i - 1][j];    //세로, 대각
                if (arr[i - 1][j] != 1 && arr[i][j - 1] != 1) {
                    for (int k = 0; k < 3; k++) {
                        dp[2][i][j] += dp[k][i - 1][j - 1];        //가로, 세로, 대각
                    }
                }
            }
        }
    }
 
    int ans = 0;
    for (int i = 0; i < 3; i++) {
        ans += dp[i][N][N];
    }
 
    cout << ans;
}
 
//#include <iostream>
//
//using namespace std;
//
//int N;
//int arr[16][16];
//int dp[3][16][16];
//int dx[3] = { 1,0,1 };
//int dy[3] = { 0,1,1 };
//
//void dfs(int state, int y, int x)
//{
//    if (dp[state][y][x] != -1) return;
//
//    int cur = 0;
//
//    if (state != 1 && arr[y][x + 1] == 0 && x + 1 < N) {
//        dfs(0, y, x + 1);
//        cur += dp[0][y][x + 1];
//    }
//
//    if (state != 0 && arr[y + 1][x] == 0 && y + 1 < N) {
//        dfs(1, y + 1, x);
//        cur += dp[1][y + 1][x];
//    }
//
//    bool flag = true;
//
//    for (int i = 0; i < 3; i++) {
//        int yy = y + dy[i];
//        int xx = x + dx[i];
//        if (arr[yy][xx] != 0) {
//            flag = false;
//            break;
//        }
//    }
//
//    if (flag && x + 1 < N && y + 1 < N) {
//        dfs(2, y + 1, x + 1);
//        cur += dp[2][y + 1][x + 1];
//    }
//
//    dp[state][y][x] = cur;
//}
//
//int main()
//{
//    cin >> N;
//    for (int i = 0; i < N; i++) {
//        for (int j = 0; j < N; j++) {
//            cin >> arr[i][j];
//            for (int k = 0; k < 3; k++) {
//                if (i == N - 1 && j == N - 1) {
//                    dp[k][i][j] = 1;
//                }
//                else {
//                    dp[k][i][j] = -1;
//                }
//            }
//        }
//    }
//
//    dfs(0, 0, 1);
//
//    cout << dp[0][0][1];
//}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11054번 - 가장 긴 바이토닉 부분 수열 (C++)  (0) 2022.06.05
[ 백준 ] 11779번 - 최소비용 구하기 2 (C++)  (0) 2022.06.04
[ 백준 ] 9251번 - LCS (C++)  (0) 2022.06.02
[ 백준 ] 15686번 - 치킨 배달 (C++)  (0) 2022.06.01
[ 백준 ] 1149번 - RGB거리 (C++)  (0) 2022.05.31
반응형

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

 

16946번: 벽 부수고 이동하기 4

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

매 벽마다 움직일 수 있는 공간을 체크하게 되면은 최악의 경우 O(N*M*N*M)이 되어서 시간 초과가 날 확률이 높기 때문에 배열을 한 번만 돌면서 문제를 해결할 방법을 찾아야 했습니다.

 

일단 값을 입력받고, 전체 배열을 돌면서 값이 '1'인 좌표에는 최종 정답 배열에 1을 더해주었고, '0'인 좌표마다 모두 들러서 빈 공간의 개수를 체크했습니다. 

 

그리고 빈 공간에 방문할 때마다 방문을 체크해주기 위해 배열 값을 'a'로 경신해 주었습니다.

 

또한 벽을 만나게 되면 벽의 좌표를 vect배열에 넣어주고 bfs함수의 마지막에 각 좌표에 카운트한 값을 더해주었습니다.

위 과정을 거치면 아래와 같은 결과를 얻을 수 있습니다.

모든 좌표에 대해 위의 과정을 거치면 다음과 같은 결과를 얻을 수 있습니다.

arr 배열
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
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
 
using namespace std;
 
int N, M;
char arr[1001][1001];                            //값을 입력 받을 배열
int ans[1001][1001];                            //정답을 기록할 배열
int visited[1001][1001];                        //방문을 체크할 배열
int dy[4] = { -1,1,0,0 };                        //방향 배열
int dx[4] = { 0,0,-1,1 };
 
struct pos {
    int y;
    int x;
};
 
void bfs(int y, int x)
{
    queue<pos> q;
    vector<pos> vect;
 
    q.push({ y,x });
    arr[y][x] = 'a';
 
    int cnt = 1;
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int yy = curY + dy[i];
            int xx = curX + dx[i];
            if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (arr[yy][xx] == '0') {
                    arr[yy][xx] = 'a';                                //배열값을 'a'로 초기화하면서 다시 방문하지 못하게 한다.
                    cnt++;                                            //갈 수 있는 곳의 수를 저장
                    q.push({ yy,xx });
                }
                if (arr[yy][xx] == '1' && visited[yy][xx] != 1) {    //벽을 만나면 visited에 기록하고 좌표를 저장
                    visited[yy][xx] = 1;
                    vect.push_back({ yy,xx });
                }
            }
        }
    }
 
    for (int i = 0; i < vect.size(); i++) {
        int yy = vect[i].y;
        int xx = vect[i].x;
        visited[yy][xx] = 0;                        //방문 기록을 없애고
        ans[yy][xx] += cnt;                            //해당 좌표에 cnt값을 더해줌
    }
}
 
int main()
{
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == '0') {
                bfs(i, j);                            //해당 배열의 값이 '0'이라면
            }                                        //bfs를 돌린다
            else if (arr[i][j] == '1') {
                ans[i][j]++;                        //해당 값이 '1'이라면 총 카운트 수에서 1을 더해준다
            }
        }
    }
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cout << ans[i][j] % 10;                    //10으로 나눈 나머지 값을 출력한다.
        }
        cout << endl;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1509번 - 팰린드롬 분할 (C++)  (0) 2022.05.26
[ 백준 ] 1208번 - 부분수열의 합 2 (C++)  (0) 2022.05.25
[ 백준 ] 17387번 - 선분 교차 2 (C++)  (0) 2022.05.24
[ 백준 ] 17143번 - 낚시왕 (C++)  (0) 2022.05.23
[ 백준 ] 12100번 - 2048(Easy) (C++)  (0) 2022.05.21

+ Recent posts

티스토리툴바