백준 10026 적록색약(JAVA) - BFS

백준 10026번

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

10026번: 적록색약

문제설명

적록색약이 아닌사람(A) 적록색약인 사람(B)과 이 봤을때의 그림의 그룹의 개수를 나누는 문제

A는 R,G,B 각각의 그룹을 나눌수 있지만 B는 R,G가 같게 보인다는 가정.

 

 

접근

BFS로 접근

 

코드

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

public class Main {

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static char[][] map;
    static boolean[][] visit;
    static Queue<int[]> q = new LinkedList<>();
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());
        map = new char[n][n];
        visit = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            String temp = br.readLine();
            for (int j = 0; j < n; j++) {
                map[i][j] = temp.charAt(j);
            }
        }

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visit[i][j]) {
                    cnt++;
                    bfs(i, j);
                }
            }
        }

        sb.append(cnt + " ");
        cnt = 0;
        visit = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visit[i][j]) {
                    cnt++;
                    bfs(i, j);
                }
            }
        }
        sb.append(cnt);
        System.out.println(sb);
    }

    public static void bfs(int x, int y) {
        q.offer(new int[]{x, y});
        visit[x][y] = true;
        while (!q.isEmpty()) {
            int[] t = q.poll();
            int cx = t[0];
            int cy = t[1];

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

                if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                if (visit[nx][ny] || map[cx][cy] != map[nx][ny]) continue;
                visit[nx][ny] = true;
                q.offer(new int[]{nx, ny});
            }
            if (map[cx][cy] == 'G')
                map[cx][cy] = 'R';
        }
    }
}

 

 

이슈

---

문제 풀대 static으로 n선언해주고 아래에서 int n으로 지역변수 선언해서 계속 값이 25가 나와서 헤맸다..;;

(오타는 옆에서 누가 봐주는게 빠를듯...)