[백준 10029/JAVA] 적록색약

문제

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

10026번: 적록색약

풀이

2178번 미로탐색, 2667번 단지번호붙이기와 마찬가지로 이 문제도 bfs를 이용하면 된다.

자세한 코드 설명은 링크 참조

 

bfs를 진행하며 그림이 몇 개의 영역으로 보이는지 출력.

bfs : 인접한 좌표에 현재 색과 같은 색이 있으면 방문한다.

두 가지 결과를 출력해야 한다.

1. 적록색약이 아닌 경우
   arr초기화 -> (0,0)부터 탐색 시작, 방문 안 한 좌표 bfs탐색  -> bfs 탐색 한 번 끝날 때마다 count++
2. 적록색약인 경우
   위와 같은 과정을 진행하며 count++
   단, R과 G를 같은 글자 취급하는 조건을 추가

먼저 1번을 수행한 후 결과를 StringBuilder에 append한다.
R을 G로 대체한 후 visited 배열, count변수를 재사용하기위해 초기화한다.
마찬가지로 같은 동작을 수행하여 결과를 append한다.

코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static Queue<Coordinate> q = new LinkedList<>();
    static int N;
    static String[][] arr;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        arr = new String[N][N];
        visited = new boolean[N][N];
        int count = 0;

        for(int i=0; i<N; i++){
            String str = br.readLine();
            for(int j=0; j<N; j++){
                arr[i][j] = String.valueOf(str.charAt(j));
            }
        }

        //arr[0][0]부터 탐색하면서 R, G, B 각각 bfs탐색
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(!visited[i][j]) {
                    bfs(i, j); //적록색약 X
                    count++;
                }
            }
        }

        sb.append(count).append(" ");
        count = 0; //갱신
        visited = new boolean[N][N]; //갱신

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++) {
                if (!visited[i][j]) {
                    if(arr[i][j].equals("R"))
                        arr[i][j] = "G"; //R을 G로 대체
                }
            }
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(!visited[i][j]) {
                    bfs(i, j); //적록색약 X
                    count++;
                }
            }
        }

        sb.append(count);

        bw.write(sb+" ");
        bw.close();

    }

    static void bfs(int x, int y) {

        int[] dx = {0,0,1,-1};
        int[] dy = {1,-1,0,0};

        q.offer(new Coordinate(x, y));
        visited[x][y] = true;

        while (!q.isEmpty()) {
            Coordinate c = q.poll();

            for(int i=0; i<4; i++) {
                int newX = c.x + dx[i];
                int newY = c.y + dy[i];

                if (newX < 0 || newX >= N || newY < 0 || newY >= N)
                    continue;
                if (visited[newX][newY] || !arr[newX][newY].equals(arr[c.x][c.y])) 
                    continue;

                q.offer(new Coordinate(newX, newY));
                visited[newX][newY] = true;
            }
        }
    }
}

class Coordinate{
    int x, y;

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

Note

• 조건문에서 String을 !=로 비교했다가 값이 안 걸러짐. equals()를 사용하자
• 성능 비교:

  

visited배열, count변수를 재사용할 생각을 못 하고 각각 한 개씩 선언

(visited배열 두 개를 생성하여 bfs에 인자로 전달)

StringBuilder을 사용하지 않고 각각  BufferedWriter에 담음

 

visited배열, count변수 한 개만 선언하고 재사용

StringBuilder에 append한 후 BufferedWriter로 출력

 

-> 메모리, 수행시간 모두 개선