[백준] 10026 적록색약 - BFS JAVA

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

10026번: 적록색약

코드설명

BFS 문제입니다.

 

1. 적록색약이 아닌경우,

2. 적록색약인경우

이 2가지 케이스를 모두 BFS를 진행하면 됩니다.

 

이 과정에서 HashSet을 활용했습니다.

 

오류가 났었던 부분은 적록색약인경우 

'R'일때만 'G'를 넣는것이 아닌, 'G'일때도 'R'을 넣어줘야합니다... 

이를 통해서 'R'이 먼저 나오는것이 아닌 'G'가 먼저 나올때도 같이 BFS를 그룹을 잡아줍니다.

이런점들을 계속해서 놓치는데, 문제를 명확히 이해하지 않고 코딩을 하여서 생기는 문제점으로 이런 사항들을 유의해야할 것 같습니다.

for(int i=0;i<N;i++) {
    for(int j=0;j<N;j++) {
        if(Indexing[i][j] == 0) {
            HashSet<Character> hashset = new HashSet<Character>();
            hashset.add(map[i][j]);
            if(map[i][j] == 'R') {
                hashset.add('G');	
            }else if(map[i][j] == 'G') { //이걸 생각못했습니다.
                hashset.add('R');
            }

            simulate(new Node(i, j, hashset));	
        }
    }
}

 

도움받은 TC, 아래의 TC를 보고서 'G'일때도 Hashset에 'R'을 넣어줘야한다는것을 꺠달았습니다.

3
GBG
GBG
RRR

answer :
4 2

도움받은글:  https://www.acmicpc.net/board/view/108547

 

코드

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

public class Main {
	
	public static int N;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static char[][] map;
	public static int[][] Indexing;
	public static int indexNum=1;
	public static int answer=0;
	public static int firstanswer=0, secondanswer = 0;;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	map = new char[N][N];
    	Indexing = new int[N][N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		map[i] = st.nextToken().toCharArray();
    	}
    	
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<N;j++) {
    			if(Indexing[i][j] == 0) {
    				HashSet<Character> hashset = new HashSet<Character>();
    				hashset.add(map[i][j]);
    				simulate(new Node(i, j, hashset));	
    			}
    		}
    	}
    	firstanswer = indexNum - 1;
    	
    	indexNum = 1;
    	Indexing = new int[N][N];
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<N;j++) {
    			if(Indexing[i][j] == 0) {
    				HashSet<Character> hashset = new HashSet<Character>();
    				hashset.add(map[i][j]);
    				if(map[i][j] == 'R') {
    					hashset.add('G');	
    				}else if(map[i][j] == 'G') { //이걸 생각못했습니다.
    					hashset.add('R');
    				}
    			
    				simulate(new Node(i, j, hashset));	
    			}
    		}
    	}
    	secondanswer = indexNum - 1;
    	System.out.println(firstanswer + " "+ secondanswer);
    	
    	
    }
    
    public static void simulate(Node start) { //일반
    	Queue<Node> q = new LinkedList<>();
    	q.offer(start);
    	Indexing[start.r][start.c]= indexNum;
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int r = temp.r;
    		int c = temp.c;
    		HashSet<Character> hashset = temp.hashset;
    		for(int dir=0;dir<4;dir++) {
    			int nr = r + dx[dir];
    			int nc = c + dy[dir];
				if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
				if(Indexing[nr][nc] > 0) continue;
				if(hashset.contains(map[nr][nc])) {
					Indexing[nr][nc] = indexNum;
					q.offer(new Node(nr, nc, hashset));
				}    			
    		}
    	}
    	indexNum += 1;
    }
    
}

class Node{
	int r;
	int c;
	HashSet<Character> hashset = new HashSet<Character>();
	public Node(int r, int c, HashSet<Character> hashset) {
		this.r = r;
		this.c = c;
		this.hashset = hashset;
	}
}