[BaekJoon] #1012 유기농 배추

문제이해

이 문제는 배추흰나비가 되고싶은 배추흰지렁이의 먹고사는 이야기 ..

배추흰나비가 되고싶은 배추흰지렁이는 연속된 배추를 보호할 수 있는데, 2차원 배열에 배추의 위치가 주어지고, 배추흰지렁이가 총 몇마리 필요한지 구하는 문제입니다.

문제풀이 포인트

2차원 배열에서 점 이동하는 방법
2차원 배열이 주어지고, 연속된 원소의 덩어리 개수 세기 -> DFS / BFS 을 이용한다!
BFS사용 시 Queue<int[]>로 큐 생성

문제접근

테스트의 갯수, 밭의 가로 세로의 길이가 주어지고, 배추가 심어져 있는 위치의 개수가 주어집니다.

• 문제를 풀기 위해 2차원 배열인 board을 생성하고, 배추의 위치정보를 입력받아 board 배열에 저장해줍니다.

• board의 모든 위치를 순회하며, 배추가 존재하고, 아직 방문하지 않은 위치에 대해 DFS를 수행하며 count 변수를 통해 연결된 배추그룹의 수를 카운트해주면 됩니다.

2차원 배열에서 좌표값 이동

2차원 배열에서 특정 기준으로 이동하기 위해서는 방향배열을 만들어주어야 합니다.

배열에서 특정 기준으로 이동하기 위해서는 아래와 같은 방법을 이용하면 됩니다.

// 위, 아래, 왼쪽, 오른쪽 이동 -> 문제 요구사항(조건)에 따라 변할 수 있음
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1}; 

// 현재 좌표 기준으로 위, 아래, 왼쪽, 오른쪽을 다 방문처리 해야한다고 가정
for(int i=0; i<4; i++) {
				
    // point.x, point.y는 현재 좌표
    // mx, my 이동할 좌표
	int mx = point.x + dx[i];
	int my = point.y + dy[i];
    
    
}

이 문제에서는, 현재의 위치 (x,y) 에서 상하좌우에 해당하는 위치인 (x-1,y), (x,y-1), (x+1,y), (x,y+1) 를 탐색해주어야 하므로, 다음과 같이 방향배열을 생성해주었습니다.

이렇게 생성한 방향배열의 인덱스별로 값을 참조하여 현재위치인 (x,y) 에 더해주어 원하는 위치로 점의 위치를 계산할 수 있습니다.

for문을 통해 방향배열의 증분값을 인덱스별로 가져와 계산해주면 됩니다.

중요한점은, board 외부의 점을 탐색하지 않고 oard 내부의 점 안에서만 탐색을 수행할 수 있도록 옮긴 좌표의 위치값이 좌표의 가로세로 내부의 값이 되도록 조건을 걸어주어야 합니다.

처음 문제를 봤을땐 DFS로 풀었는데 BFS로도 풀 수 있다고 해서 둘 다 구현해보았습니다.

BFS

좌표 처리를 위해 선언 시 큐의 자료형을 Queue<Integer> 이 아닌 Queue<int[]>로 설정해주어야 합니다.

DFS

code

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

public class Main{
        static int[][] board;
        static boolean[][] visited;
        static int[] dx = {-1,1,0,0};
        static int[] dy = {0,0,1,-1};
        static int N;
        static int M;


        public static void main(String[] args) throws IOException{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int T = Integer.parseInt(br.readLine());
            StringTokenizer st ;

            for(int i=0; i<T; i++){
                // 테스트 갯수만큼 반복
                st = new StringTokenizer(br.readLine());
                M = Integer.parseInt(st.nextToken());
                N = Integer.parseInt(st.nextToken());
                int K = Integer.parseInt(st.nextToken());

                board = new int[M][N];
                visited = new boolean[M][N];
                // 배추의 위치 표시
                for(int j=0; j<K; j++){
                    st = new StringTokenizer(br.readLine());
                    int X = Integer.parseInt(st.nextToken());
                    int Y = Integer.parseInt(st.nextToken());
                    board[X][Y] = 1;
                }

                int count =0;
                // board 탐색하며 DFS를 시작할 배추위치 찾기
                for(int a=0; a<M; a++){
                    for(int b=0; b<N;b++ ){
                        if(board[a][b] == 1 && !visited[a][b] ){
                            // DFS(a,b);
                             BFS(a,b);
                            count ++;
                        }
                    }
                }
                System.out.println(count);
            }
        }

        static void BFS(int X, int Y){
            Queue<int[]> q = new LinkedList<int[]>();
            q.add(new int[] {X,Y});
            visited[X][Y] = true;
            while(!q.isEmpty()){
                X = q.peek()[0];
                Y = q.peek()[1];
                visited[X][Y] = true;
                q.poll();
                for(int i=0; i<4; i++){
                    int MX = X + dx[i];
                    int MY = Y + dy[i];
                if( MX >= 0 && MX < M && MY >= 0 && MY < N){
                    if(board[MX][MY] == 1 && !visited[MX][MY]){
                        q.add(new int[] {MX, MY});
                        visited[MX][MY] = true;
                    }
                }

                }
            }
        }
        static void DFS(int X, int Y){
            visited[X][Y] = true;
            // 현재 좌표를 기준으로 상하좌우를 살피고,
            for(int i=0; i<4; i++) {
                int MX = X + dx[i];
                int MY = Y + dy[i];

            // 이동시킨 점의 위치가 배추밭 내부의 점이여야 한다
            if( MX >= 0 && MX < M && MY >= 0 && MY < N){
                // 만약 해당 값이 방문하지 않은 점이고, 값이 1이라면 return
                if(board[MX][MY] == 1 && !visited[MX][MY]){
                    DFS(MX,MY);
                }
            }

        }
    }
}