[JAVA] 백준 10026 적록색약

문제 링크 : https://www.acmicpc.net/problem/10026 

10026번: 적록색약

 

골드 문제 치고 간단한 BFS 문제였습니다. 

 

1. R, G, B로 나누어져 있을때의 덩어리 갯수(cnt)를 구하기

2. G -> R로 변경하여 R과 B로 나누어졌을때 덩어리갯수(cntRG) 구하기

 

문제풀이 초기 설정을 위와 같이 잡고 문제를 풀었습니다.

핵심이 되는 bfs는 초기 시작점인 Point p와 bfs중 방문하는 nr, nc의 map 값이 같을때만 진행하도록 하였습니다.

코드로 보면 map[nr][nc] == map[p.x][p.y]가 되겠네요

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

public class Main {
    static int N, cnt, cntRG;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static char[][] map;
    static boolean[][] visit;

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

        N = Integer.parseInt(br.readLine());
        map = new char[N][N];
        visit = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            map[i] = str.toCharArray();
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visit[i][j]) {
                    bfs(new Point(i, j));
                    cnt++;
                }
            }
        }
        
        // G -> R로 바꾸기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 'G') {
                    map[i][j] = 'R';
                }
            }
        }
        
        // 방문 배열 초기화
        visit = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visit[i][j]) {
                    bfs(new Point(i, j));
                    cntRG++;
                }
            }
        }

        System.out.println(cnt + " " + cntRG);
    }

	// bfs 시작점인 p와 같을때만 방문처리하도록
    static void bfs(Point p) {
        Queue<Point> queue = new LinkedList<>();
        queue.add(p);
        visit[p.x][p.y] = true;
        while (!queue.isEmpty()) {
            Point now = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nr = now.x + dr[i];
                int nc = now.y + dc[i];
                if (nr < 0 || nc < 0 || nr >= N || nc >= N || visit[nr][nc] || map[nr][nc] != map[p.x][p.y]) {
                    continue;
                }
                queue.add(new Point(nr, nc));
                visit[nr][nc] = true;
            }
        }
    }

	// 확인용 print 메서드
    static void print() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}

 

많이 부족한 코드입니다. 수정할 점, 잘못된 점, 개선점 보이면 말씀해주세요!!

감사합니다.