[백준] code.plus(BFS 알고리즘,JAVA)10026번, 적록색약

문제 링크

10026번: 적록색약

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

그래프 알고리즘이란?

각 정점과 연결하는 선분의 정보를 가지고 BFS(너비 우선 탐색), DFS(깊이 우선 탐색) .... 등을 이용하여 정점에서 다른 정점으로 가는 최소값, 최대값 등의 문제에서 출력하라는 결과를 구하는 알고리즘입니다.

 

BFS?

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 적록색약인 사람은 빨간색과 초록색을 하나의 색깔로 본다.

2. 일반인과 적록색약을 가진 사람이 그림을 볼 때 색깔의 구역의 개수를 결과로 출력합니다.

 

일반인

BFS탐색을 통해서 그림에 대한 색깔에 각 구역을 구해서 결과로 출력한다.

 

적록색약을 가진 사람

탐색을 진행하기 전 그림에서 R(빨간색) -> G(초록색)으로 변경한 뒤 탐색을 진행하여 각 구역의 개수를 결과로 출력한다.

 

※적록색약인은 빨간색과 초록색을 같은색으로 구분하기 때문에 하나의 색깔로 바꾼 것입니다.

 

 

예제입력 1.

 

그림을 본 일반인이 나눈 구역

R	R	R	B	B
G	G	B	B	B
B	B	B	R	R
B	B	R	R	R
R	R	R	R	R

 

구역 : 4개

 

그림을 본 적록색맹이 나눈 구역

G	G	G	B	B
G	G	B	B	B
B	B	B	G	G
B	B	G	G	G
G	G	G	G	G

구역 : 3개

 

결과로 4, 3을 순서대로 출력한다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 그림에 대한 정보를 저장하였습니다.
• 그림의 각 위치에서 구역을 탐색하는 bfs함수를 호출하는 search함수를 실행하였습니다.
• 일반인이 본 구역의 개수, 적록색맹이 본 구역의 개수를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search는 그림의 각 자리에서 구역을 나누도록 bfs함수를 호출하는 함수입니다.
• bfs함수는 입력받은 위치에서 현재 구역을 묶도록 BFS 탐색을 진행하는 함수입니다.
• colorChange는 그림에 색을 R -> G로 바꾸는 함수입니다.

 

import java.util.*;
import java.io.*;

public class Main {
	//그림 좌표 관련 클래스
    static class position{
        int x,y;
        public position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int N;
    static char[][] art;	//그림 색깔 저장 배열
    static boolean[][] visited;	//그림 방문 확인 배열
    static int[] dx = {0,0,-1,1};	//상하좌우 X값 변경
    static int[] dy = {-1,1,0,0};	//상하좌우 Y값 변경
    static public void  main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        N = Integer.parseInt(br.readLine());
        art = new char[N][N];
        //그림에 대한 색 저장
        for(int i=0;i<N;i++){
            String str = br.readLine();
            for(int j=0;j<N;j++)
                art[i][j] = str.charAt(j);
        }
        bw.write(search() + " ");	//일반인 시점 구역 개수 BufferedWriter 저장
        colorChange();		//R -> G 바꾸어서 적록색맹 시점으로 변경
        bw.write(search() + "\n");	//적록색맹 시점 구역 개수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //그림의 각 위치를 기준으로 구역을 BFS함수를 호출하는 함수
    static int search(){
        visited = new boolean[N][N];
        int count = 0;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(!visited[i][j]){
                    bfs(j,i,art[i][j]);
                    count++;
                }
            }
        }
        return count;
    }
    //BFS탐색으로 해당 구역을 나눈다.
    static void bfs(int x, int y, char color){
        Queue<position> queue = new LinkedList<>();
        visited[y][x] = true;
        queue.add(new position(x,y));
        while(!queue.isEmpty()){
            position cur = queue.poll();
            for(int i=0;i<4;i++){
                int tempX = cur.x + dx[i];
                int tempY = cur.y + dy[i];
                if(tempX>=0 && tempY>=0 && tempX<N && tempY<N && !visited[tempY][tempX]){
                    if(art[tempY][tempX] == color){
                        visited[tempY][tempX] = true;
                        queue.add(new position(tempX,tempY));
                    }
                }
            }
        }

    }
    //R -> G로 바꾸는 함수
    static void colorChange() {
        for (int i = 0; i < N; i++) {
            for(int j=0;j<N;j++){
                if(art[i][j] == 'R')
                    art[i][j] = 'G';
            }
        }
    }
}