[BFS] 백준 2573번 빙산 - JAVA

 

 

오늘도 1문제 클리어!!

이번에는 답 안보고 내 힘으로 풀어서 더 뿌듯했다 헤헤

이 빙산 문제는 옛날에 내가 풀었던 치즈 문제와 비슷하게 느껴졌다.

 

[BFS] 백준 2638번 치즈 - JAVA

 

현재에 본가에 있는 나는 동생 컴퓨터를 빌려쓰고 있는데,

여기는 이클립스나 java 컴파일이 될 수 있는 환경이 없어서 아래 컴파일러 사이트를 이용했다.

 

새 Java 프로그램 만들기 - 마이컴파일러 - myCompiler

 

 

---

1. 문제 출처

---

 

 

2573번: 빙산

 

 

 

 

 

 

---

2. 설계

---

 

일단 전제 조건을 잘 확인한다. 무조건 빙하 한 덩이로 시작한다는 문구가 제시되어 있어 처음부터 빙하가 나뉘어져 있는지 확인할 필요가 없다.

 

 

1. 빙하 녹여주기  (BFS)

빙하를 녹여줄 때 1이상인 곳이 빙하이므로 그 곳을 탐색해서 주변에 0이 있는 곳을 count해 1씩 줄여주는 방법을 생각하는 사람이 많을 것이다. 하지만 이 문제는 오히려 0인 곳을 넣어줘야 한다.

 

int year = 0;
visited = new boolean[n][m];

melting:for(int i=0;i<n;i++){
	for(int j=0;j<m;j++){
		if(map[i][j]==0 && !visited[i][j]){
			BFS(i, j);
		}
	}
}// melting end

year++;

 

• 빙하 map의 모든 곳을 돌면서 0인 곳 중 아직 방문하지 않은 곳을 대상으로 BFS를 돈다.

 

//빙하 깎기
public static void BFS(int startR, int startC){
	Queue<Node> q = new LinkedList<>();
	q.offer(new Node(startR, startC));
	visited[startR][startC] = true;

	while(!q.isEmpty()){
		Node curNode = q.poll();

		for(int d=0;d<4;d++){
			int nextR = curNode.r+drc[d][0];
			int nextC = curNode.c+drc[d][1];

			if(nextR<0 || nextR>=n || nextC<0 || nextC>=m) continue;
			if(visited[nextR][nextC]) continue;

			if(map[nextR][nextC]>0){
				map[nextR][nextC]--;
				if(map[nextR][nextC]==0) visited[nextR][nextC] = true;
			}

			else if(map[nextR][nextC]==0){
				visited[nextR][nextC] = true;
				q.offer(new Node(nextR, nextC));
			}
                
		}// for d end
            
	}// while end
}

 

• 첫 시작점과 사방으로 연결되어 있는 모든 해수를 큐에 넣어주며 주변에 빙하가 있으면 녹여준다.
• 녹인 빙하가 0이 되어 해수가 되었다면 visited를 true로 해서 다른 빙하에 영향을 받지 않게 해준다.
• 큐에서 꺼낸 위치에서 4방 조사를 하며 해수를 발견했다면 visited를 true로 해서 큐에 중복으로 들어가지 않게 해준다.

 

 

2. 빙하가 2개 이상으로 분리되었는가?  (BFS)

빙하를 녹인 후 2개 이상으로 분리되었는지 확인한다. 1이상인 곳이 빙하이기 때문에 그곳을 시작으로 주변 빙하 뭉텅이를 체크하는 것이다. 그 뭉텅이를 모두 계산할 필요는 없다. 2개째 되는 빙하가 확인되는 순간 멈춰주면 된다.

 

//check seperate
//빙하가 부숴졌냐? BFS
count = 0;
visited = new boolean[n][m];
check:for(int a=0;a<n;a++){
	for(int b=0;b<m;b++){
		if(map[a][b]>0 && !visited[a][b]){
			if(count>1){
				break check;
			}
			else{
				Seperate(a,b);
				count++;
			}
		}
                    
	}
} // for a end

 

• 이런식으로 count가 1개 이상이 확인되는 순간 멈춰주면 된다.

 

//빙하가 두동강 났니?
public static void Seperate(int startR, int startC){
	Queue<Node> q = new LinkedList<>();
	q.offer(new Node(startR, startC));
	visited[startR][startC] = true;

	while(!q.isEmpty()){
		Node curNode = q.poll();

		for(int d=0;d<4;d++){
			int nextR = curNode.r+drc[d][0];
			int nextC = curNode.c+drc[d][1];

			if(nextR<0 || nextR>=n || nextC<0 || nextC>=m) continue;
			if(visited[nextR][nextC]) continue;

			if(map[nextR][nextC]>0){
				visited[nextR][nextC] = true;
				q.offer(new Node(nextR, nextC));
			}
                
		}// for d end
            
	}// while end
}

 

• 빙하가 분리되었는지 한 뭉텅이를 확인하는 BFS이다.
• 위에 빙하를 녹이는 BFS 함수와 매우 유사하다. 다른 점은 map[nextR][nextC] > 0 이 부분만 체크해준다는 점이다.

 

 

3. 빙하가 분리되지 않았다면?

빙하가 분리되지 않았다면 다시 1~2번 과정을 반복해주면 된다. 그래서 while문을 이용한다.

 

while(count==1){
	//1번과정

	//2번과정
}

 

• count == 1일 경우에만 무한 반복을 돌려주는 것이다.
• count == 0일 경우에는 빙하가 다 녹았다는 것이다.
• count > 1일 경우에는 빙하가 분리되었다는 것이다.

 

 

4. 결과 출력

 

if(count==0) System.out.println(0);
else System.out.println(year);

 

• 그래서 count가 0이면 빙하가 모두 녹았다는 뜻이므로 결과 0을 출력한다.
• 그렇지 않다면 빙하가 분리된 최초 년도 year을 출력한다.

 

 

 

---

3. 전체 코드

---

import java.io.*;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;

class Main {

    static boolean[][] visited;
    static int[][] drc = {{-1,0},{1,0},{0,-1},{0,1}};
    static int n;
    static int m;
    static int[][] map;
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //1. 입력
        String n_m = br.readLine();
        StringTokenizer st = new StringTokenizer(n_m, " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        map = new int[n][m];
        for(int i=0;i<n;i++){
            String numLine = br.readLine();
            st = new StringTokenizer(numLine, " ");

            for(int j=0;j<m;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }// for end


        //2. 빙하 깎기
        int year = 0;
        int count = 1; //빙하 수

        while(count==1){
            visited = new boolean[n][m];
            melting:for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    if(map[i][j]==0 && !visited[i][j]){
                        BFS(i, j);
                    }
                }
            }// melting end
            year++;

            //check seperate
            //빙하가 부숴졌냐? BFS
            count = 0;
            visited = new boolean[n][m];
            check:for(int a=0;a<n;a++){
                for(int b=0;b<m;b++){
                    if(map[a][b]>0 && !visited[a][b]){
                        if(count>1){
                            break check;
                        }
                        else{
                            Seperate(a,b);
                            count++;
                        }
                    }
                    
                }
            } // for a end
        }

        if(count==0) System.out.println(0);
        else System.out.println(year);
    }

    //빙하 깎기
    public static void BFS(int startR, int startC){
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(startR, startC));
        visited[startR][startC] = true;

        while(!q.isEmpty()){
            Node curNode = q.poll();

            for(int d=0;d<4;d++){
                int nextR = curNode.r+drc[d][0];
                int nextC = curNode.c+drc[d][1];

                if(nextR<0 || nextR>=n || nextC<0 || nextC>=m) continue;
                if(visited[nextR][nextC]) continue;

                if(map[nextR][nextC]>0){
                    map[nextR][nextC]--;
                    if(map[nextR][nextC]==0) visited[nextR][nextC] = true;
                }

                else if(map[nextR][nextC]==0){
                    visited[nextR][nextC] = true;
                    q.offer(new Node(nextR, nextC));
                }
                
            }// for d end
            
        }// while end
    }

    //빙하가 두동강 났니?
    public static void Seperate(int startR, int startC){
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(startR, startC));
        visited[startR][startC] = true;

        while(!q.isEmpty()){
            Node curNode = q.poll();

            for(int d=0;d<4;d++){
                int nextR = curNode.r+drc[d][0];
                int nextC = curNode.c+drc[d][1];

                if(nextR<0 || nextR>=n || nextC<0 || nextC>=m) continue;
                if(visited[nextR][nextC]) continue;

                if(map[nextR][nextC]>0){
                    visited[nextR][nextC] = true;
                    q.offer(new Node(nextR, nextC));
                }
                
            }// for d end
            
        }// while end
    }
    
    public static class Node{
        int r;
        int c;
        public Node(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
}

 

 

BFS 중복 코드가 많다...