BOJ::2573 빙산

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


코드도 길고 문제도 어려워 보이지만,

조건 하나하나 함수로 구현해서 종합하면 풀리는 문제.

팁은 문제로 주어지는 2차원배열에서 1행,1열,n행,m열은 무조건 0인점을 이용해 반복문을 줄이는것.


<JAVA>


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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    
    static int n,m,ax,ay;
    static int dx[]={1,-1,0,0};
    static int dy[]={0,0,1,-1};
    static int map[][];
    static int tmp[][];
    static boolean visited[][];
    
    public static void main(String args[]) throws NumberFormatException, IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n=Integer.parseInt(st.nextToken());
        m=Integer.parseInt(st.nextToken());
        map=new int[n][m];
        tmp=new int[n][m];
        
        for(int i = 0 ; i < n ; i++){
            if(i==0 || i==n-1){
                br.readLine();
                continue;
            }
            st = new StringTokenizer(br.readLine());
            for(int j = 0 ; j < m ; j++){
                if(j==0 || j==m-1){
                    st.nextToken();
                    continue;
                }
                map[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        
        int time=0;
        while(true){
            //빙산 개수
            int parts = getParts();
            if(parts>=2){
                System.out.println(time);
                break;
            }else if(parts==0){
                System.out.println(0);
                break;
            }
            
            time++;
            //녹이기
            for(int i = 1; i < n-1 ; i++){
                for(int j = 1 ; j < m-1 ; j++){
                    if(map[i][j]>0){
                        tmp[i][j]=melt(i,j);
                    }
                }
            }
            //녹인거 적용시키기
            for(int i = 1 ; i < n-1 ; i++){
                for(int j = 1 ; j < m-1 ; j++){
                    if(map[i][j]>0){
                        map[i][j]-=tmp[i][j];
                        if(map[i][j]<0){
                            map[i][j]=0;
                        }
                    }
                }
            }
        }
    }
    //빙산 덩어리 몇개인지 개수 반환
    public static int getParts(){
        visited = new boolean[n][m];
        int cnt=0;
        for(int i = 1 ; i < n-1 ; i++){
            for(int j =1 ; j < m-1 ; j++){
                if(map[i][j]>0 && !visited[i][j]){
                    dfs(i,j);
                    cnt++;
                }
            }
        }
        return cnt;
    }
    //빙산 덩어리가 몇개인지 확인을 위한 탐색
    public static void dfs(int x,int y){
        visited[x][y]=true;
        for(int i = 0; i < 4 ; i++){
            ax = x+dx[i];
            ay = y+dy[i];
            if(!visited[ax][ay] && map[ax][ay]>0){
                dfs(ax,ay);
            }
        }
    }
    //빙산 녹이기
    public static int melt(int x,int y){
        int cnt=0;
        for(int i = 0 ; i < 4 ; i++){
            ax = x+dx[i];
            ay = y+dy[i];
            if(map[ax][ay]==0){
                cnt++;
            }
        }
        return cnt;
    }
    //상태확인용
    public static void show(){
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
    }
}
cs



<C++>


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
#include <iostream>
#include <string>
using namespace std;
 
int n, m, ax, ay;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int map[300][300];
int tmp[300][300];
bool visited[300][300];
 
void show() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
}
 
void dfs(int x, int y) {
    visited[x][y] = true;
    for (int i = 0; i < 4; i++) {
        ax = x + dx[i];
        ay = y + dy[i];
        if (map[ax][ay] > 0 && !visited[ax][ay]) {
            dfs(ax, ay);
        }
    }
}
 
int getParts() {
    for (int i = 1; i < n - 1; i++) {
        for (int j = 1; j < m - 1; j++) {
            visited[i][j] = false;
        }
    }
    int cnt = 0;
    for (int i = 1; i < n - 1; i++) {
        for (int j = 1; j < m - 1; j++) {
            if (map[i][j] > 0 && !visited[i][j]) {
                dfs(i, j);
                cnt++;
            }
        }
    }
    return cnt;
}
 
int melt(int x, int y) {
    int cnt = 0;
    for (int i = 0; i < 4; i++) {
        ax = x + dx[i];
        ay = y + dy[i];
        if (map[ax][ay] == 0) {
            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 time = 0;
    while (true) {
        //빙산 개수
        int parts = getParts();
        if (parts >= 2) {
            cout << time << endl;
            break;
        }
        else if (parts == 0) {
            cout << 0 << endl;
            break;
        }
 
        time++;
 
        //녹이기
        for (int i = 1; i < n - 1; i++) {
            for (int j = 1; j < m - 1; j++) {
                if (map[i][j] > 0) {
                    tmp[i][j] = melt(i, j);
                }
            }
        }
        //녹인거 적용시키기
        for (int i = 1; i < n - 1; i++) {
            for (int j = 1; j < m - 1; j++) {
                if (map[i][j] > 0) {
                    map[i][j] -= tmp[i][j];
                    if (map[i][j] < 0) {
                        map[i][j] = 0;
                    }
                }
            }
        }
    }
 
}
cs


저작자표시

'BOJ::문제풀이' 카테고리의 다른 글

2589 보물섬  (0) 2018.01.04
2579 계단 오르기  (0) 2018.01.04
2563 색종이  (0) 2018.01.01
2309 일곱 난쟁이  (0) 2018.01.01
2293 동전 1  (0) 2018.01.01

+ Recent posts

티스토리툴바