반응형

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

 

11400번: 단절선

첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

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

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
struct Edge {
    int start;
    int end;
};
 
bool cmp(Edge left, Edge right)
{
    if (left.start == right.start) return left.end < right.end;
    return left.start < right.start;
}
 
int V, E;
vector<int> list[100001];
int id[100001];
vector<Edge> ans;
int cur = 1;
 
int dfs(int node, int parent)
{
    id[node] = cur++;
    int ret = id[node];
 
    for (auto next : list[node]) {
        if (next == parent) continue;    //부모를 제외하고
        if (id[next]) {
            ret = min(ret, id[next]);
            continue;
        }
 
        int minId = dfs(next, node);    //갈 수 있는 가장 낮은 id
 
        if (minId > id[node]) {    //간선을 오름차순으로 정렬
            ans.push_back({ min(node,next), max(node,next) });
        }
 
        ret = min(ret, minId);
    }
    return ret;
}
 
int main()
{
    scanf("%d %d", &V, &E);
 
    for (int i = 0; i < E; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        list[a].push_back(b);
        list[b].push_back(a);
    }
 
    for (int i = 1; i <= V; i++) {
        if (!id[i]) {
            dfs(i, 0);
        }
    }
 
    sort(ans.begin(), ans.end(), cmp);    //시작 간선을 기준으로 오름차순 정렬
 
    printf("%d\n", ans.size());
 
    for (auto edge : ans) {
        printf("%d %d\n", edge.start, edge.end);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 16637번 - 괄호 추가하기 (C++)  (0) 2022.08.31
[ 백준 ] 2178번 - 미로 탐색 (C++)  (0) 2022.08.30
[ 백준 ] 11266번 - 단절점 (C++)  (0) 2022.08.27
[ 백준 ] 3653번 - 영화 수집 (C++)  (0) 2022.08.25
[ 백준 ] 1153번 - 길의 개수 (C++)  (0) 2022.08.24
반응형

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

 

14942번: 개미

자연수 n이 주어진다. n은 방의 개수이다. (1 ≤ n ≤ 105) 다음 n개의 줄에는 차례대로 현재 각각의 개미가 보유하고 있는 에너지 값이 주어진다. i+1번째 줄에는 i번째 방에 있는 개미가 가진 에너

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/95?category=1073064 

 

[ 자료구조 ] 희소 배열(Sparse Table)

1. 희소 배열(Sparse Table) - 배열 원소의 개수가 무조건 배열의 length 값보다 작은 배열 - 희소 배열은 배열의 원소 위치가 연속적이지 않은 배열 2. 희소 배열 만들기 보통 5번 노드에서 1번 노드까

rudalsd.tistory.com

 

1. 희소 배열을 이용하여 n번 이동했을 때의 노드와 거리를 저장

 

2. n번 이동했을 때 거리가 현재 가지고 있는 에너지보다 작다면 이동

 

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
74
75
76
77
78
79
80
81
82
83
#include<iostream>
#include<vector>
#include<cmath>
 
using namespace std;
 
struct node {
    int to;
    int dist;
};
 
int n;
int energy[100001];
vector<node> list[100001];
int visited[100001];
int arr[100001][17];
int dist[100001][17];
int H;
 
void dfs(int cur)    //그래프 그리기
{
    if (visited[cur] == 1) return;
    visited[cur] = 1;
 
    for (auto next : list[cur]) {
        if (visited[next.to] == 1) continue;
        arr[next.to][0] = cur;
        dist[next.to][0] = next.dist;
        dfs(next.to);
    }
}
 
void makeTree()        //트리 만들기
{
    for (int i = 1; i < H; i++) {        //순서 중요!!!
        for (int j = 2; j <= n; j++) {
            int next = arr[j][i - 1];
            if (arr[next][i - 1] == 0) continue;
            arr[j][i] = arr[next][i - 1];
            dist[j][i] = dist[next][i - 1] + dist[j][i-1];
        }
    }
}
 
int getRomm(int cur)    //최종 도달 방 찾기
{
    int ret = cur;
    int E = energy[cur];
    for (int i = H - 1; i >= 0; i--) {
        if (arr[ret][i] != 0 && dist[ret][i] <= E) {
            E -= dist[ret][i];        //순서 중요!!!
            ret = arr[ret][i];
        }
        if (ret == 1 || E == 0) break;
    }
 
    return ret;
}
 
int main()
{
    scanf("%d", &n);
    H = ceil(log2(n));
 
    for (int i = 1; i <= n; i++) {
        scanf("%d", &energy[i]);
    }
 
    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 });
    }
 
    dfs(1);
 
    makeTree();
 
    for (int i = 1; i <= n; i++) {
        printf("%d\n", getRomm(i));
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1932번 - 정수 삼각형 (C++)  (0) 2022.08.11
[ 백준 ] 17401번 - 일하는 세포 (C++)  (0) 2022.08.10
[ 백준 ] 13141번 - Ignition (C++)  (0) 2022.08.08
[ 백준 ] 7578번 - 공장 (C++)  (0) 2022.08.07
[ 백준 ] 16287번 - Parcel (C++)  (0) 2022.08.06
반응형

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

 

10026번: 적록색약

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

각각의 문자에 따라 구역을 0으로 바꿔주는 함수를 만들어서 적록색약이 아닌 사람이 볼 수 있는 구역의 수를 구해줍니다. 그리고 R과 G를 한 구역으로 찾는 함수를 하나 더 만들어주어서 적록색약인 사람이 볼 수 있는 구역의 수를 출력해줍니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
 
struct node {
    int y;
    int x;
};
 
void bfs(int y, int x, char ch, char temp[][101])
{
    queue<node> q;
    q.push({ y,x });
    temp[y][x] = 0;
 
    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        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 < N) {
                if (temp[yy][xx] == ch) {
                    temp[yy][xx] = 0;
                    q.push({ yy,xx });
                }
            }
        }
    }
}
 
void bfsRG(int y, int x, char temp[][101])
{
    queue<node> q;
    q.push({ y,x });
    temp[y][x] = 0;
 
    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        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 < N) {
                if (temp[yy][xx] == 'R' || temp[yy][xx] == 'G') {
                    temp[yy][xx] = 0;
                    q.push({ yy,xx });
                }
            }
        }
    }
}
 
int main()
{
    scanf("%d", &N);
 
    char arr[101][101];
    char temp[101][101];
 
    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++) {
            temp[i][j] = arr[i][j];
        }
    }
 
    int cnt = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (temp[i][j] == 'R') {
                cnt++;
                bfs(i, j, 'R', temp);
            }
            else if (temp[i][j] == 'G') {
                cnt++;
                bfs(i, j, 'G', temp);
            }
            else if (temp[i][j] == 'B') {
                cnt++;
                bfs(i, j, 'B', temp);
            }
        }
    }
 
    printf("%d ", cnt);
 
    cnt = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == 'R' || arr[i][j] == 'G') {
                cnt++;
                bfsRG(i, j, arr);
            }
            else if (arr[i][j] == 'B') {
                cnt++;
                bfs(i, j, 'B', arr);
            }
        }
    }
 
    printf("%d", cnt);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 7578번 - 공장 (C++)  (0) 2022.08.07
[ 백준 ] 16287번 - Parcel (C++)  (0) 2022.08.06
[ 백준 ] 11438번 - LCA 2 (C++)  (0) 2022.08.04
[ 백준 ] 1725번 - 히스토그램 (C++)  (0) 2022.08.03
[ 백준 ] 6549번 - 히스토그램에서 가장 큰 직사각형 (C++)  (0) 2022.08.02
반응형

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

 

11725번: 트리의 부모 찾기

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

먼저 vector를 이용하여 그래프 입력을 받고, 입력받은 그래프를 바탕으로 DFS를 돌려 문제를 풀 수 있습니다. 한번 방문한 노드는 다시 방문할 필요가 없으므로 visited배열을 통해 방문 체크를 해주시면 됩니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N;
vector<int> list[100001];
int visited[100001];
int parent[100001];
 
void dfs(int node)
{
    if (visited[node] == 1) return;
    visited[node] = 1;
 
    for (auto next : list[node]) {
        if (visited[next] != 1) {
            parent[next] = node;
            dfs(next);
        }
    }
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        list[a].push_back(b);
        list[b].push_back(a);
    }
 
    dfs(1);
 
    for (int i = 2; i <= N; i++) {
        printf("%d\n", parent[i]);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 6549번 - 히스토그램에서 가장 큰 직사각형 (C++)  (0) 2022.08.02
[ 백준 ] 1629번 - 곱셈 (C++)  (0) 2022.08.01
[ 백준 ] 11444번 - 피보나치 수 6 (C++)  (0) 2022.07.30
[ 백준 ] 2243번 - 사탕상자 (C++)  (0) 2022.07.29
[ 백준 ] 5719번 - 거의 최단 경로 (C++)  (0) 2022.07.27
반응형

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

 

1167번: 트리의 지름

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지

www.acmicpc.net

 

 

[ 문제풀이 ]

 

풀이 방법을 생각해내는데 시간이 조금 걸렸지만 방법만 알아낸다면 매우 쉬운 문제였습니다.

 

먼저 지름은 어떤 점에서 출발하던 지 가장 먼 곳에 있습니다. 이를 이용하여 먼저 한 점에서 가장 먼 점을 찾고, 그 점으로부터 가장 먼 점을 찾으면 지름을 구할 수 있습니다.

 

[ 소스 코드 ]

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
#include <iostream>
#include <vector>
#include <cstring>
 
using namespace std;
 
struct node {
    int to;
    int dist;
};
 
int V;
vector<node> list[100001];
int visited[100001];
int startNode;
int ans;
 
void dfs(int num, int dist)            //시작점으로부터 가장 먼 노드와 거리를 저장
{
    if (visited[num] == 1) {
        return;
    }
    visited[num] = 1;
 
    if (ans < dist) {
        ans = dist;
        startNode = num;
    }
 
    for (int i = 0; i < list[num].size(); i++) {
        int next = list[num][i].to;
        int nextDist = list[num][i].dist;
        dfs( next, dist + nextDist );
    }
}
 
int main()
{
    cin >> V;
 
    for (int i = 0; i < V; i++) {
        int n;
        cin >> n;
        while (1) {
            int to;
            scanf("%d", &to);
            if (to != -1) {
                int dist;
                scanf("%d", &dist);
                list[n].push_back({ to,dist });
            }
            else {
                break;
            }
        }
    }
 
    dfs(1, 0);        //1번 노드에서 가장 먼 노드 저장
    memset(visited, 0, sizeof(visited));
    dfs(startNode, 0);    //시작 노드부터 가장 먼 노드와 거리 저장
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14003번 - 가장 긴 증가하는 부분 수열 5 (C++)  (0) 2022.06.21
[ 백준 ] 9328번 - 열쇠 (C++)  (0) 2022.06.20
[ 백준 ] 17404번 - RGB거리 2 (C++)  (0) 2022.06.18
[ 백준 ] 7662번 - 이중 우선순위 큐 (C++)  (0) 2022.06.17
[ 백준 ] 1967번 - 트리의 지름 (C++)  (0) 2022.06.16
반응형

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

 

1967번: 트리의 지름

파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연

www.acmicpc.net

 

 

[ 문제풀이 ]

 

풀이 방법을 생각해내는데 시간이 조금 걸렸지만 방법만 알아낸다면 매우 쉬운 문제였습니다.

 

먼저 지름은 어떤 점에서 출발하던 지 가장 먼 곳에 있습니다. 이를 이용하여 먼저 한 점에서 가장 먼 점을 찾고, 그 점으로부터 가장 먼 점을 찾으면 지름을 구할 수 있습니다.

 

[ 소스 코드 ]

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<vector>
#include<cstring>
 
using namespace std;
 
struct Node {
    int to;
    int dist;
};
 
int n;
 
vector<Node> list[10001];
int visited[10001];
int snode;
int diameter;
 
void dfs(int num, int dist)
{
    if (visited[num] == 1) {
        return;
    }
 
    if (diameter < dist) {
        diameter = dist;
        snode = num;
    }
 
    visited[num] = 1;
 
    for (int i = 0; i < list[num].size(); i++) {
        int next = list[num][i].to;
        int nextDist = list[num][i].dist;
        dfs(next, dist + nextDist);
    }
}
 
int main()
{
    cin >> n;
 
    for (int i = 0; i < n-1; i++) {
        int p, c, d;
        scanf("%d %d %d", &p, &c, &d);
        list[p].push_back({ c,d });
        list[c].push_back({ p,d });
    }
 
    dfs(1, 0);        //한 노드에서 가장 먼 노드를 찾기
 
    memset(visited, 0, sizeof(visited));
 
    dfs(snode, 0);    //위에서 찾은 노드에서 가장 먼 노드를 찾기
 
    cout << diameter;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17404번 - RGB거리 2 (C++)  (0) 2022.06.18
[ 백준 ] 7662번 - 이중 우선순위 큐 (C++)  (0) 2022.06.17
[ 백준 ] 13549번 - 숨바꼭질 3 (C++)  (0) 2022.06.15
[ 백준 ] 9935번 - 문자열 폭발 (C++)  (0) 2022.06.14
[ 백준 ] 2638번 - 치즈 (C++)  (0) 2022.06.13
반응형

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

 

2638번: 치즈

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로

www.acmicpc.net

 

 

[ 문제풀이 ]

 

BFS를 이용한 구현 문제였습니다.

 

주어진 모눈종이의 테두리는 치즈가 없다고 하였으므로 0, 0부터 BFS를 돌려 치즈로 둘러싸여 있지 않은 공간들을 2로 초기화시켜주고 치즈들 중 2칸 이상 2에 닿아있는 치즈는 녹이면서 진행하였습니다.

 

그리고 다시 0, 0부터 BFS를 돌려 빈 공간들을 2로 초기화시켜주면서 위의 과정을 반복하고, 치즈가 다 사라지면 BFS를 돌린 횟수를 출력하였습니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<queue>
#include<cstring>
 
using namespace std;
 
int N, M;
int map[100][100];
int visited[100][100];
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)        //치즈에 둘러쌓여 있지 않은 공간을 2로 초기화
{
    queue<pos> q;
    memset(visited, 0, sizeof(visited));
    q.push({ y,x });
    visited[y][x] = 1;
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        map[curY][curX] = 2;
 
        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 (map[yy][xx] != 1 && visited[yy][xx] != 1) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                }
            }
        }
    }
}
 
int check()        //치즈가 다 녹았는지 체크하는 함수
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 1) {
                return 0;
            }
        }
    }
 
    return 1;
}
 
int Cnt(int y, int x)    //실내 온도에 노출 된 횟수를 출력
{
    int cnt = 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 (map[yy][xx] == 2) {
                cnt++;
            }
        }
    }
 
    return cnt;
}
 
int main()
{
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }
 
    int cnt = 0;
 
    while (!check())        //치즈가 다 녹을 때까지
    {
        bfs(0, 0);        //0, 0부터 2로 빈 공간 2로 초기화
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 1) {    //2칸 이상 닿아있다면 녹임
                    if (Cnt(i, j) >= 2) {
                        map[i][j] = 0;
                    }
                }
            }
        }
 
        cnt++;        //횟수 추가
    }
 
    cout << cnt;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 13549번 - 숨바꼭질 3 (C++)  (0) 2022.06.15
[ 백준 ] 9935번 - 문자열 폭발 (C++)  (0) 2022.06.14
[ 백준 ] 13460번 - 구슬 탈출 2 (C++)  (0) 2022.06.12
[ 백준 ] 11404번 - 플로이드 (C++)  (0) 2022.06.11
[ 백준 ] 1865번 - 웜홀 (C++)  (0) 2022.06.10
반응형

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

티스토리툴바