[백준](Java) 10026 - 적록색약

26579 단어 BFSJava백준BFS

문제 링크

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

문제 풀이

간단한 bfs 문제들은 기본 뼈대는 똑같고 특정 부분에서의 로직이 다른것 같다.
이문제도 기본 bfs 문제의 뼈대와 거의 유사하지만
적록 색맹이라는 사람이 R,G를 구분없이 인식한다는 점이 똑같았다.
그래서 bfs를 총 2번 돌렸는데 정상인일때와, 적록색맹일때를 나눴고 이를 bfs에 넘겨줄때 k값으로 해서 구분 지었다.

정상인의 경우는 일반 bfs와 똑같지만 적록색맹인 경우 가지고 현재의 색깔이 R,G인 경우에는 RG에 대해서 contain조건으로 접근했다.

else{
	if(color.equals("R")||color.equals("G")){
           color = "RG"
        }
        if (!chk[now_y][now_x] && color.contains(map[now_y][now_x])) {
           queue.add(new Node(now_y, now_x));
           chk[now_y][now_x] = true;
        }
}

코드

import java.util.*;

public class Main {

    static int n;
    static int m;
    static int normal;
    static int abnormal;

    static String[][] map;
    static boolean[][] chk;
    static boolean[][] chk2;

    static int[] diry = {-1, 0, 1, 0};
    static int[] dirx = {0, 1, 0, -1};

    static class Node {
        int y;
        int x;

        public Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        String[] line = new String[n];
        for (int i = 0; i < n; i++) {
            line[i] = sc.next();
        }
        m = line[0].length();
        map = new String[n][m];
        chk = new boolean[n][m];
        chk2 = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            String[] value = line[i].split("");
            for (int j = 0; j < value.length; j++) {
                map[i][j] = value[j];
            }
        }

        for (int k = 0; k < 2; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (!chk[i][j]) {
//                        System.out.println(i + " " + j);
                        bfs(i, j, k, map[i][j]);
                    }
                }
            }
            for (int p = 0; p < n; p++) {
                Arrays.fill(chk[p], false);
            }
        }
        System.out.println(normal + " " + abnormal);
//        System.out.println(Arrays.deepToString(map));
    }

    public static void bfs(int y, int x, int idx, String color) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(y, x));
        chk[y][x] = true;
        while (!queue.isEmpty()) {
            Node now = queue.poll();
            for (int i = 0; i < 4; i++) {
                int now_y = now.y + diry[i];
                int now_x = now.x + dirx[i];
                if (now_y >= 0 && now_y < n && now_x >= 0 && now_x < m) {
                    if (idx == 0) {
                        if (!chk[now_y][now_x] && map[now_y][now_x].equals(color)) {
                            queue.add(new Node(now_y, now_x));
                            chk[now_y][now_x] = true;
                        }
                    }else{
                        if(color.equals("R")||color.equals("G")){
                            color = "RG";
                        }
                        if (!chk[now_y][now_x] && color.contains(map[now_y][now_x])) {
                            queue.add(new Node(now_y, now_x));
                            chk[now_y][now_x] = true;
                        }
                    }
                }
            }
        }

        if (idx == 0) {
            normal++;
        } else {
            abnormal++;
        }
    }
}

좋은 웹페이지 즐겨찾기