백준 - 1012번, 유기농 배추(sol.java)

◎문제 링크

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

1012번: 유기농 배추

---

◎문제 파악

비연결일 수도 있는 그래프를 BFS로 탐색하는 문제이다.

예를 들어 위와 같은 밭이 있고 1인 칸이 배추가 있는 칸이라면, 위의 문제는 5개의 비연결 그래프를 BFS로 탐색하는 문제이다.

 

비연결 그래프를 BFS탐색하기 위해서는

1. BFS 탐색 조건

2. 탐색이 끝날 조건

두가지가 필요하다.

 

1. BFS 탐색 조건에서는 배추 흰 지렁이가 상하좌우에 있는 인접한 배추로는 이동할 수 있으므로, 상하좌우에 있는 배추들끼리 연결 그래프로 묶으면 된다.

 

2. 탐색이 끝날 조건, 즉 모든 비연결 그래프를 탐색했다는 보장을 하기 위해서는 각 배추가 흰지렁이를 가지고 있는지 확인하면 된다.

 

그러므로, TotalQueue에 좌표를 저장해두고, 각 TotalQueue를 poll하면서, poll된 좌표가 처음 도착한 연결 그래프의 일부라면 배추흰벌레를 poll된 좌표에 넣어주고(answer++), 연결그래프의 나머지에도 배추 흰벌레가 서식한다고 생각하였다.(같은 연결 그래프의 또 다른 배추를 다시 탐색해도 answer값이 증가하지 않음)

---

◎코드 구현

package project;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main{
    //field[배추밭의 1차원 크기][배추밭의 2차원 크기][0:배추인지 아닌지(1,0),1:배추흰지렁이가 있는지 없는지(1,0)]
    int[][][] field;
    Queue<Integer> firstCoordinate = new LinkedList<>(); //1차원 좌표 저장큐(임시)
    Queue<Integer> secondCoordinate = new LinkedList<>(); //2차원 좌표 저장큐(임시)
    
    Queue<Integer> fullFirstCoordinate = new LinkedList<>(); //1차원 좌표 저장큐(total)
    Queue<Integer> fullSecondCoordinate = new LinkedList<>(); //2차원 좌표 저장큐(total)
    
    public static void main(String[] args) throws IOException{
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        for(int i = 0; i<N; i++){
            Main m = new Main();
            
            String[] inputTmp = (br.readLine()).split(" ");
            m.field = new int[Integer.parseInt(inputTmp[1])][Integer.parseInt(inputTmp[0])][2]; //필드 초기화
            for(int j = 0; j<Integer.parseInt(inputTmp[2]); j++){
                String[] inputTmp2 = (br.readLine()).split(" ");
                int firstDimension = Integer.parseInt(inputTmp2[1]);
                int secondDimension = Integer.parseInt(inputTmp2[0]);
                //필드에 배추의 위치를 표시해준다
                m.field[firstDimension][secondDimension][0] = 1;
                //좌표 저장큐에 배추의 좌표를 넣어준다
                m.fullFirstCoordinate.add(firstDimension);
                m.fullSecondCoordinate.add(secondDimension);
            }
            
            System.out.println(m.organicCabbage());
            
        }

    }
    
    public int organicCabbage(){
        int answer = 0;
        
        //모든 배추를 둘러볼때, 배추는 있는데 배추흰지렁이가 없으면 배추에 배추 흰지렁이를 넣어주고 answer++;
        while(!fullFirstCoordinate.isEmpty()){
            int firstDimension = fullFirstCoordinate.poll();
            int secondDimension = fullSecondCoordinate.poll();
            
            
            if(field[firstDimension][secondDimension][1]==0){
                field[firstDimension][secondDimension][1]=1;
                answer++;
                //배추 흰지렁이가 상하좌우에 있는 배추로 퍼져나가게 한다.
                BFS(firstDimension, secondDimension);
            }
            
        }
        
        return answer;
    }
    
    //BFS로 배추 주변을 살펴본다
    public void BFS(int firstDimension, int secondDimension){
        firstCoordinate.add(firstDimension);
        secondCoordinate.add(secondDimension);
        
        while(!firstCoordinate.isEmpty()){            
            
            firstDimension = firstCoordinate.poll();
            secondDimension = secondCoordinate.poll();
            
            move(firstDimension, secondDimension,0 ,-1);
            move(firstDimension, secondDimension, 0 , 1);
            move(firstDimension, secondDimension, 1 , 0);
            move(firstDimension, secondDimension, -1 ,0);
            
        }
    }
    
    //현재 배추의 상하좌우가 배추이고, 배추 지렁이가 없다면 지렁이 추가
    public void move(int firstDimension, int secondDimension, int a, int b){
        
        int forwardFirstDimension = firstDimension + a;
        int forwardSecondDimension = secondDimension + b;
        
        if(isIn(forwardFirstDimension, forwardSecondDimension)){
            if(field[forwardFirstDimension][forwardSecondDimension][0]==1 &&
              field[forwardFirstDimension][forwardSecondDimension][1]==0){
                field[forwardFirstDimension][forwardSecondDimension][1]=1;
                firstCoordinate.add(forwardFirstDimension);
                secondCoordinate.add(forwardSecondDimension);
            }
        }
    }
    
    //좌표를 움직일때 field를 벗어나지 않는지 알려주는 메서드
    public boolean isIn(int a, int b){
        if(a>=0 && a<field.length && b>=0 && b< field[0].length){
            return true;
        }
        return false;
    }
}

이론상으로는 totalQueue, temporaryQueue 두가지만 필요하지만, x좌표값(firstDimenstion)과 y좌표값(secondDimension)을 가진 int[2] 배열을 매번 만드는 것이 부담스러워서,

x좌표값에 대한 totalQueue,

y좌표값에 대한 totalQueue,

x좌표값에 대한 temporaryQueue,

y좌표값에 대한 temporayQueue

4개가 생겼다.

---

DFS와 BFS 카테고리 문제를 거의 다 풀어간다. BFS를 확실히 더 많이 사용하는 것 같다. 나머지 문제도 화이팅