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

 

14501번: 퇴사

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

www.acmicpc.net

N의 범위가 1부터 15이므로 완전 탐색으로 쉽게 풀어줄 수 있다.

1부터 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
#include <cstdio>
using namespace std;
 
int n;
int max;
int t[16];
int p[16];
 
void solve(int index, int sum) {
    if(index > n) {
 
        //퇴사하는 날짜가 되었으면 최댓값을 계산
 
        if(max < sum) {
            max = sum;
        }
        return;
    }
 
 
    //index번째 날짜에 상담을 하지 않는 경우
    solve(index+1,sum);
 
 
    //퇴사하는 날(n+1)을 넘어가지 않는 경우에만 index번째 날 상담을 진행
    if(index+t[index] <= n+1)
        //상담에 소요되는 날짜와 수익을 더해서 넘겨준다
        solve(index+t[index],sum+p[index]);
 
}
 
int main() {
 
    scanf("%d", &n);
 
    for(int i=1; i<=n; i++) {
        scanf("%d %d", &t[i],&p[i]);
    }
 
 
    max = 0;
    solve(1,0);
    printf("%d", max);
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2206. 벽 부수고 이동하기  (0) 2019.06.28
[BOJ] 3055. 탈출  (0) 2019.06.27
[BOJ] 1697. 숨바꼭질  (0) 2019.06.27
[BOJ] 7569. 토마토 (3차원)  (0) 2019.06.27
[BOJ] 7576. 토마토  (0) 2019.06.27

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

 

1697번: 숨바꼭질

문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지

www.acmicpc.net

수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 구하는 문제이므로 bfs를 사용하면 된다.

수빈이가 갈 수 있는 모든 칸(정점)으로 1초마다 이동하고 방문한 칸은 가지 않는다.(최소 시간이 아니기 때문)

 

먼저 수빈이의 위치 n을 큐에 넣어주고 문제에 나온  x-1, x+1, 2*x 로 각각 이동해준다.(범위를 벗어나지 않는다면)

방문한 경우 visit배열에 걸린 시간을 저장해주고 큐에 넣어준다.

동생의 위치에 도착한 경우(visit[k]에 이동 시간이 저장되어 초기값 -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
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
 
 
 
int main() {
    int n, k;
    int visit[100001];
    memset(visit,-1,sizeof(visit));
    
    scanf("%d %d", &n, &k);
 
    queue<int> q;
 
 
    //수빈이의 위치
    q.push(n);
    visit[n] = 0;
 
 
    //bfs
    while(!q.empty()) {
        int x = q.front();
        q.pop();
 
 
        //x-1로 가는 경우
        //먼저 범위 체크후에 방문하지 않았으면 방문
        if(x-1 >= 0) {
            if(visit[x-1] == -1) {
                q.push(x-1);
                visit[x-1] = visit[x] + 1;
            }
        }
        
 
        //x+1로 가는 경우
        //먼저 범위 체크 후에 방문하지 않았으면 방문
        if(x+1 < 100001) {
            if(visit[x+1] == -1) {
                q.push(x+1);
                visit[x+1] = visit[x] + 1;
            }
        }
        
 
        //2*x로 가는 경우
        //먼저 범위 체크 후에 방문하지 않았으면 방문
        if(2*x < 100001) {
 
            if(visit[2*x] == -1) {
                q.push(2*x);
                visit[2*x] = visit[x] + 1;
            }
        }
        
 
        //동생의 위치에 도착했으면 더 탐색하지 않는다.
        if(visit[k] != -1) {
            break;
        }
 
    }
 
    
    printf("%d", visit[k]);
    return 0;
 
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 3055. 탈출  (0) 2019.06.27
[BOJ] 14501. 퇴사  (0) 2019.06.27
[BOJ] 7569. 토마토 (3차원)  (0) 2019.06.27
[BOJ] 7576. 토마토  (0) 2019.06.27
[BOJ] 11724. 연결 요소의 개수  (0) 2019.06.27

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

 

7569번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마

www.acmicpc.net

7576번 문제와 거의 똑같은 문제인데 범위가 조금 더 적고 대신에 상자가 3차원이다.

처음에 똑같은 상자가 h만큼 있는걸로 문제를 오해해서 잘못 풀었었다...;;

7576번 문제에서 3차원으로만 바꿔주면 되지만 나는 c++에 아직 익숙하지 않아서 조금 어려움을 겪었다ㅠㅠ

 

먼저 큐에 저장 하는 방식

2차원에서는 x와 y좌표만 넣어주면 되므로 pair를 사용하였지만 이 문제에서는 z좌표 까지 함께 넣어야한다.

처음에는 tuple을 사용하려 했지만 값을 받아오는 방법이 불편해서 다들 pair를  이중으로 쓴다길래 따라했다..

 

queue<pair<pair<int,int>, int>> q;

 

이런식으로 pair를 중첩해서 넣어줬다. (x, y) 가 먼저 pair 가 되고, (x, y) 가 다시 z와 pair가 된다.

이렇게 pair만 3차원 방식에 맞게 구현해주면 나머지는 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
77
78
79
80
81
#include <cstdio>
#include <queue>
using namespace std;
int n,m,h;
int box[100][100][100];
int day[100][100][100];
int dx[] = {0,0,1,-1,0,0};
int dy[] = {1,-1,0,0,0,0};
int dz[] = {0,0,0,0,1,-1};
 
 
int main() {
 
    scanf("%d %d %d", &m, &n, &h);
    queue<pair<pair<int,int>,int> > q;
 
 
    for(int k=0; k<h; k++) {
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
 
                scanf("%d", &box[i][j][k]);
                day[i][j][k] = -1;
                //익은 토마토인 경우 큐에 넣는다.
                if(box[i][j][k] == 1) {
                    q.push(make_pair(make_pair(i,j),k));
                    day[i][j][k] = 0;
                }
             
            }
        }
    }
  
 
    while(!q.empty()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int z = q.front().second;
        q.pop();
 
        for(int i=0; i<6; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            int nz = z+dz[i];
            
            //범위 체크
            if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if(nz < 0 || nz >= h) continue;
 
            //안익은 토마토 && 아직 방문 안함
            if(box[nx][ny][nz] == 0 && day[nx][ny][nz] == -1) {
                q.push(make_pair(make_pair(nx,ny),nz));
                day[nx][ny][nz] = day[x][y][z] + 1;
            }
        }
 
    }
 
 
    int ans = 0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            for(int k=0; k<h; k++) {
                if(box[i][j][k] == 0 && day[i][j][k] == -1) {
                    ans = -1;
                    break;
                }
 
                if(ans < day[i][j][k])
                    ans = day[i][j][k];
            }
            if(ans == -1) break;
            
        }
        if(ans == -1) break;
    }
 
    printf("%d", ans);
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 14501. 퇴사  (0) 2019.06.27
[BOJ] 1697. 숨바꼭질  (0) 2019.06.27
[BOJ] 7576. 토마토  (0) 2019.06.27
[BOJ] 11724. 연결 요소의 개수  (0) 2019.06.27
[BOJ] 2178. 미로 탐색  (0) 2019.06.25

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

 

7576번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마

www.acmicpc.net

이 문제는 전형적인 bfs 문제이다.

상자에 있는 토마토가 상하좌우로 하루에 하나씩 익어가는데 모든 토마토가 익는데 걸리는 최소 일수를 구해야 하므로 bfs를 사용하면 된다.

기존에 익어있는 토마토로부터 익으므로 입력받을 때 익은 토마토인 경우 바로 큐에 넣어준다.

상하좌우를 탐색하며 방문하지 않은 토마토에 방문하여 소요 날짜를 저장한다.

 

 

탐색이 끝난 이후에는 문제의 조건에 따라 토마토가 모두 익지는 못하는 상황이라면 -1을 출력하기 위해서

안 익은 토마토인데 방문하지 않은 토마토를 찾는다. 혹시 존재한다면 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
#include <cstdio>
#include <queue>
using namespace std;
int n,m;
int box[1000][1000];
int day[1000][1000];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
 
 
int main() {
 
    scanf("%d %d", &m, &n);
    queue<pair<int,int> > q;
 
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            scanf("%d", &box[i][j]);
 
            //익는데 걸리는 날짜를 저장할 배열 -1로 초기화
            day[i][j] = -1;
 
            //익은 토마토인 경우 큐에 넣는다.
            if(box[i][j] == 1) {
                q.push(make_pair(i,j));
                day[i][j] = 0;
            }
        }
    }
 
 
    //bfs
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for(int i=0; i<4; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
 
            //범위 체크
            if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
 
            //안익은 토마토 && 아직 방문 안함
            if(box[nx][ny] == 0 && day[nx][ny] == -1) {
                q.push(make_pair(nx,ny));
 
                //소요 일수를 저장 (이전 칸보다 하루 증가)
                day[nx][ny] = day[x][y] + 1;
            }
        }
 
    }
 
 
    //탐색 종료 후에 안익은 토마토가 있는지를 검사 
    int ans = 0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
 
            //안 익은 토마토가 있는데 방문하지 않았다.
            if(box[i][j] == 0 && day[i][j] == -1) {
                ans = -1;
                break;
            }
 
 
            //가장 마지막에 익은 토마토의 날짜를 구해야하므로
            //최댓값을 ans에 저장한다. 
            if(ans < day[i][j])
                ans = day[i][j];
        }
        //위의 반복문에서 안익은 토마토가 있는 경우 빠져나와서 break
        if(ans == -1) break;
    }
 
    printf("%d", ans);
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 1697. 숨바꼭질  (0) 2019.06.27
[BOJ] 7569. 토마토 (3차원)  (0) 2019.06.27
[BOJ] 11724. 연결 요소의 개수  (0) 2019.06.27
[BOJ] 2178. 미로 탐색  (0) 2019.06.25
[BOJ] 4963. 섬의 개수  (0) 2019.06.25

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

 

11724번: 연결 요소의 개수

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

www.acmicpc.net

제목대로 연결 요소의 개수를 구하는 문제인데 배열 형태가 아니므로 각 정점을 인접 리스트로 구현해준다.

나는 int형 벡터를 갖는 배열로 구현하였다.

간선의 개수만큼 반복문을 실행하여 정점을 입력받아 u리스트에는 v를 추가하고 v리스트에는 u를 추가한다.

 

한 번 bfs를 시작할때 연결된 정점을 모두 방문한다. 즉, bfs가 한번 도는게 연결 요소 1개인 셈이다.

그러므로 모든 방문하지 않은 정점을 방문해서 bfs가 새로 실행될 때마다 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
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
bool check[1000];
vector<int> list[1000];
 
void bfs(int x) {
    queue<int> q;
    q.push(x);
    check[x] = true;
 
    while(!q.empty()) {
        x = q.front();
        q.pop();
 
 
        //연결된 정점들을 검사
        for(int k=0; k<list[x].size(); k++) {
            int y = list[x][k];
            if(check[y] == false) {
                q.push(y);
                check[y] = true;
            }
        }
    }
}
 
int main() {
 
    int n,m;
    scanf("%d %d", &n,&m);
 
 
    //인접 리스트(벡터 배열로 구현)
    for(int i=0; i<m; i++) {
        int u, v;
        scanf("%d %d", &u,&v);
        list[u].push_back(v);
        list[v].push_back(u);
    }
 
    int ans = 0;
    for(int i=1; i<=n; i++) {
        if(check[i] == false) {
            ++ans;
            bfs(i);
        }
    }
 
    printf("%d", ans);
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 7569. 토마토 (3차원)  (0) 2019.06.27
[BOJ] 7576. 토마토  (0) 2019.06.27
[BOJ] 2178. 미로 탐색  (0) 2019.06.25
[BOJ] 4963. 섬의 개수  (0) 2019.06.25
[BOJ] 2667. 단지번호붙이기  (0) 2019.06.25

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

 

2178번: 미로 탐색

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

www.acmicpc.net

이 문제는 (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제이다.

문제에서는 1, 1이라고 한 곳은 실제로는 0, 0 이므로 주의해야 한다!

마찬가지로 마지막 칸 N, M도 (N-1, M-1) 칸을 출력해주면 된다.

 

최소 칸수를 구하는 문제이므로 bfs를 사용한다.

시작칸에서 부터 갈 수 있는 칸으로 단계적으로 진행하기 때문에 최단 거리로 이동할 수 있다.

이동할 때마다 각 칸에는 해당 칸까지의 이동 횟수를 저장해준다.

그러면 최종적으로 마지막 칸에 마지막 칸까지의 최소 이동 횟수가 저장된다.

 

 

문제에 나와있는 예시를 보면 아래와 같이 지도가 있는데

1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1

 

bfs를 통해 이동 횟수를 cnt배열에 저장해주면 다음과 같다.

1 0 9 10 11 12
2 0 8 0 12 0
3 0 7 0 13 14
4 5 6 0 14 15

 

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
#include <cstdio>
#include <queue>
using namespace std;
 
int n,m;
int map[100][100];
int cnt[100][100];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
 
int main() {
    scanf("%d %d", &n,&m);
 
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
 
    queue<pair<int,int> > q;
 
    //첫번째 칸에서 시작
    q.push(make_pair(0,0));
    cnt[0][0] = 1;
 
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int k=0; k<4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if(map[nx][ny] == 1 && cnt[nx][ny] == 0) {
                q.push(make_pair(nx,ny));
 
                //이전 단계보다 1 증가(이동 횟수 증가)
                cnt[nx][ny] = cnt[x][y] + 1;
            }
        }
    }
 
    //마지막 칸을 출력
    printf("%d\n", cnt[n-1][m-1]);
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 7576. 토마토  (0) 2019.06.27
[BOJ] 11724. 연결 요소의 개수  (0) 2019.06.27
[BOJ] 4963. 섬의 개수  (0) 2019.06.25
[BOJ] 2667. 단지번호붙이기  (0) 2019.06.25
[BOJ] 14888. 연산자 끼워넣기  (0) 2019.06.20

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

 

4963번: 섬의 개수

문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.  두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는

www.acmicpc.net

단순 연결 요소 문제로 모든 정점을 탐색하는 bfs나 dfs를 사용하여 풀 수 있다.

이 문제는 대각선도 연결되어 있으므로 방향을 상, 하, 좌, 우에다가 대각선 네 방향까지 모두 탐색해주면 된다.

섬의 개수만 세면 되므로 bfs가 매번 실행될 때마다 ans값이 증가하도록 구현했다.

 

테스트 케이스의 개수가 명시되어 있지 않으므로 while문에서 w와 h값이 모두 0인 경우에 break 하도록 해주었다.

ans는 각 테스트 케이스가 끝날 때마다 출력해준다.

 

주의할 점은 ans는 while문 안에서 선언해주거나 아니면 다시 0으로 초기화되도록 해주어야 한다.

check 배열 역시 새로운 테스트 케이스에서 지도의 정보를 입력받을 때 같이 false로 초기화해준다.

 

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
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
 
int h,w;
int map[50][50];
bool check[50][50];
int dx[] = {0,0,1,-1,-1,-1,1,1};
int dy[] = {1,-1,0,0,-1,1,-1,1};
 
void bfs(int x, int y) {
    queue<pair<int,int> > q;
    q.push(make_pair(x,y));
    check[x][y] = true;
 
    while(!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        //8가지 방향으로 이동
        for(int k=0; k<8; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if(nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
 
            //땅이고, 방문하지 않았으면 방문
            if(map[nx][ny] == 1 && check[nx][ny] == false) {
                q.push(make_pair(nx,ny));
                check[nx][ny] = true;
            }
        }
    }
}
 
int main() {
    
 
    while(true) {
        int ans = 0;
        scanf("%d %d", &w,&h);
 
        if(w == 0 && h == 0) break;
 
        for(int i=0; i<h; i++) {
            for(int j=0; j<w; j++) {
                scanf("%d", &map[i][j]);
                check[i][j] = false;
            }
        }
 
        for(int i=0; i<h; i++) {
            for(int j=0; j<w; j++) {
 
                //땅이고 아직 방문하지 않았다.
                if(map[i][j] == 1 && check[i][j] == false) {
                    ans++;
                    bfs(i,j);
                }
            }
        }
 
       printf("%d\n", ans);
    }
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 11724. 연결 요소의 개수  (0) 2019.06.27
[BOJ] 2178. 미로 탐색  (0) 2019.06.25
[BOJ] 2667. 단지번호붙이기  (0) 2019.06.25
[BOJ] 14888. 연산자 끼워넣기  (0) 2019.06.20
[BOJ] 6603. 로또  (0) 2019.06.20

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

 

2667번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수

www.acmicpc.net

연결 요소를 찾는 문제이다. bfs나 dfs를 사용해서 풀 수 있다.

나는 bfs를 사용해서 풀었다.

아파트가 있고 아직 방문하지 않은(단지 번호가 붙어있지 않은) 모든 칸에 대해서 bfs를 실행해준다.

단지 번호(cnt)는 bfs가 새로 실행될때마다 증가한다.

단지 번호는 num이라는 int형 이차원 배열을 만들어서 붙여주고 이 배열을 사용하여 방문 체크도 해준다.

 

 

탐색을 모두 마쳤으면, 각 단지별 아파트 개수를 세준다.

새로운 ans 배열을 만들어서 num배열의 값을 index로 값을 증가시킨다.

즉, ans배열의 1번째에는 단지 번호가 1인 아파트의 개수가 저장되고 ans[2]에는 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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
 
int n;
int cnt;
int map[25][25];
int num[25][25];
int ans[25*25];
 
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
 
void bfs(int x, int y) {
    queue<pair<int,int> > q;
    
 
//시작칸 큐에 넣어주고 단지 번호 붙여준다.
q.push(make_pair(x,y));   
    num[x][y] = cnt;
 
    while(!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
 
        //인전한 칸으로 이동
        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            //범위 벗어나면 넘어간다.
            if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
 
            //아파트가 있고 아직 방문하지 않은 경우
            if(map[nx][ny] == 1 && num[nx][ny] == 0) {
             //큐에 넣어주고
                q.push(make_pair(nx,ny));
 
                //단지 번호를 붙여준다.
                num[nx][ny] = cnt;
            }
            
        }
    }
}
 
int main() {
 
    scanf("%d", &n);
    
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
    
    cnt = 0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
 
 
         //집이 있는 곳이고 아직 방문하지 않은 경우 bfs를 실행
            if(map[i][j] == 1 && num[i][j] == 0) {
             //다음 연결 요소 이므로 단지 번호를 늘려준다.
                ++cnt;
                bfs(i,j);
            }
            
        }
    }
 
 
    //총 단지수를 출력
    printf("%d\n", cnt);
 
 
    //각 단지 번호를 인덱스로 ans배열의 값을 증가시킨다.
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(num[i][j] != 0) {
                ans[num[i][j]] += 1;
            }
        }
    }
 
    //문제 조건에서 정렬하라고 했으므로 정렬
    sort(ans+1, ans+cnt+1);
 
    for(int i=1; i<=cnt; i++) {
        printf("%d\n",ans[i]);
    }
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2178. 미로 탐색  (0) 2019.06.25
[BOJ] 4963. 섬의 개수  (0) 2019.06.25
[BOJ] 14888. 연산자 끼워넣기  (0) 2019.06.20
[BOJ] 6603. 로또  (0) 2019.06.20
[BOJ] 10971. 외판원 순회2 (DFS 풀이)  (0) 2019.06.20

+ Recent posts

티스토리툴바