BOJ) 적록색약

적록색약

10026번: 적록색약

풀이

 

적록색약이 있는 사람이 봤을 때 영역의 갯수와 일반 사람이 봤을 때 영역의 갯수를 각각 출력하는 문제다.

가장 기본적인 grouping을 활용하는 문제였다.

코드 수를 줄이려면, 서칭하는 메소드를 하나로 합치고 식별 번호를 부여해서 if문을 통해 처리할 수 있다.

하지만, 코드의 길이가 200 300줄이 되는 정도는 아니어서 그냥 나눠서 진행했다. ( solution에서 더 깔끔하게 볼 수 있기 때문에)

 

평범한 사람이 봤을 때는, 해당 맵과 인접한 부근에 같은 색상을 가진 곳들을 grouping해주었다.

적록색약의 경우에는 파란색에서 인접한 부분에 파란색상인 곳을, 빨강과 초록에 인접한 부분에는 파랑이 아닌 곳을 grouping 했다.

groupIdx를 리턴해서 몇 개의 그룹이 생성되어 있는지를 구했고, 이를 StringBuffer에 담아서 출력했다.

 

 

코드

 

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

public class Main {
    final static int[] dx = {1,-1,0,0}, dy = {0,0,1,-1};
    final static char RED = 'R', GREEN = 'G', BLUE = 'B';
    final static int NOGROUP =0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        char[][] map = new char[n][n];
        for(int i=0; i<n; i++) {
            map[i] = br.readLine().toCharArray();
        }
        solution(n,map);
        br.close();
    }

    private static void solution(int n, char[][] map) {
        StringBuffer sb = new StringBuffer();
        sb.append(getNormal(n,map)).append(" ");
        sb.append(getRedGreen(n,map));
        System.out.println(sb.toString());
    }

    private static int getNormal(int n, char[][] map) {
        int groupIdx =0;
        int[][] group = new int[n][n];
        LinkedList<Pos> moveList = new LinkedList<>();

        for(int y=0; y<n; y++) {
            for(int x=0; x<n; x++) {
                if(group[y][x] == NOGROUP) {
                    moveList.offer(new Pos(x,y));
                    group[y][x] = ++groupIdx;
                    char origin = map[y][x];

                    while(!moveList.isEmpty()) {
                        Pos pos = moveList.poll();
                        for(int i=0; i<4; i++) {
                            int nx = pos.x +dx[i];
                            int ny = pos.y +dy[i];
                            if(isInArea(nx,ny,n)) {
                                if(map[ny][nx] == origin && group[ny][nx] ==NOGROUP) {
                                    group[ny][nx] = groupIdx;
                                    moveList.offer(new Pos(nx,ny));
                                }
                            }
                        }
                    }
                }
            }
        }
        return groupIdx;
    }

    private static int getRedGreen(int n, char[][] map) {
        int groupIdx =0;
        int[][] group = new int[n][n];
        LinkedList<Pos> moveList = new LinkedList<>();

        for(int y=0; y<n; y++) {
            for(int x=0; x<n; x++) {
                if(group[y][x] == NOGROUP) {
                    moveList.offer(new Pos(x,y));
                    group[y][x] = ++groupIdx;
                    char origin = map[y][x];

                    while(!moveList.isEmpty()) {
                        Pos pos = moveList.poll();
                        for(int i=0; i<4; i++) {
                            int nx = pos.x +dx[i];
                            int ny = pos.y +dy[i];
                            if(isInArea(nx,ny,n)) {
                                if(origin == BLUE) {
                                    if(map[ny][nx] == BLUE && group[ny][nx] == NOGROUP) {
                                        group[ny][nx] = groupIdx;
                                        moveList.offer(new Pos(nx,ny));
                                    }
                                } else {    // RED GREN
                                    if(map[ny][nx] != BLUE && group[ny][nx] == NOGROUP) {
                                        group[ny][nx] = groupIdx;
                                        moveList.offer(new Pos(nx,ny));
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        return groupIdx;
    }

    private static boolean isInArea(int x, int y, int n) {
        return x>=0 && x<n && y>=0 && y<n;
    }

    private static class Pos {
        int x,y;
        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}