BOJ) 양 한마리... 양 두마리...

양 한마리... 양 두마리...

11123번: 양 한마리... 양 두마리...

풀이

 

프로그래머스에서 grouping을 이용하는 문제를 풀어봤어서, 금방 풀었다.

내가 푼 방식은 각 위치에서 양이 있는 자리일 때, 그룹이 지정됐는지 여부를 확인하고 그룹화를 해주는 것이다.

그룹의 인덱스를 1부터 시작하면서, grouping을 해줄 때 마다, 그룹의 인덱스를 1씩 증가시켜주었다.

grouping이 끝나고 나면 group의 인덱스 = 그룹의 갯수+1 가 저장되어 있기 때문에, group 인덱스 -1을 출력하면서 답을 구해주었다.

우선순위에 따라 순수하게 DFS로만 풀어도 괜찮고, 지금과 같이 일정 구간에 대해 큐로 풀어도 괜찮다.

개인적으로는 큐로 푸는게 더 간단하다는 생각이 들어서 LinkedList를 애용하고 있다.

 

로직

 

1. 입력받는 Map을 2차원 char 배열 혹은 1차원 String 배열에 저장해준다.

 (최대 100 by 100 이기 때문에, char 배열로 저장해서 접근하는게 퍼포먼스가 더 좋을 것이라 판단했다.)

2. 맵을 돌면서 양이 있는 구역을 확인한다.

 2-1. grouping이 안되어있다면, 해당 위치에서 상하좌우를 탐색하면서 grouping을 해준다.

3. group Idx는 1부터 시작했기 때문에, 모든 맵을 탐색한 이후에는 group의 수 +1 가 저장되어 있을 것이다. 따라서, idx -1을 출력해준다.

 

코드

 

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

public class SheepGroup_11123 {
    final static char sheep = '#';
    final static int[] dx = {1,0,-1,0}, dy = {0,1,0,-1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<char[][]> sheepList = new ArrayList<>();
        int cases = Integer.parseInt(br.readLine());

        for(int i=0; i<cases; i++) {
            String sizeInfo = br.readLine();
            int ySize = Integer.parseInt(sizeInfo.split(" ")[0]);

            char[][] map = new char[ySize][];

            for(int y=0; y<ySize; y++) {
                map[y] = br.readLine().toCharArray();
            }
            sheepList.add(map);
        }

        solution(sheepList);

        br.close();
    }

    private static void solution(ArrayList<char[][]> sheepList) {
        for(char[][] sheepMap : sheepList) {
            int ySize = sheepMap.length;
            int xSize = sheepMap[0].length;
            int[][] group =new int[ySize][xSize];
            int idx =1;

            for(int y=0; y<ySize; y++) {
                for(int x=0; x<xSize; x++) {
                    if(sheepMap[y][x] == sheep && group[y][x] ==0) {
                        group = groupingSheep(group, sheepMap, idx++, x, y);
                    }
                }
            }
            System.out.println(idx-1);
        }
    }

    private static int[][] groupingSheep(int[][] group, char[][] sheepMap, int idx, int x, int y) {
        LinkedList<int[]> moveList = new LinkedList<>();
        moveList.offer(new int[]{x,y});
        group[y][x] = idx;


        while(!moveList.isEmpty()) {
            int[] pos = moveList.poll();

            for(int i=0; i<4; i++) {
                int nx = pos[0] + dx[i];
                int ny = pos[1] + dy[i];

                if(isInArea(nx,ny,sheepMap[0].length, sheepMap.length)) {
                    if(sheepMap[ny][nx] == sheep && group[ny][nx] ==0) {
                        moveList.offer(new int[] {nx,ny});
                        group[ny][nx] = idx;
                    }
                }
            }
        }
        return group;
    }

    private static boolean isInArea(int x, int y, int maxX, int maxY) {
        return x>=0 && x<maxX && y>=0 && y<maxY ? true : false;
    }
}
// https://www.acmicpc.net/problem/11123