백준 - 10026번 적록색약 - java

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

접근법

기본적인 bfs로 풀이함
그래프 자체를 두가지 버전으로 만들어서, 동일한 bfs탐색 함수를 각각 타게해서 출력시킴
처음에 메모리초과가 떠서 확인해보니

방문처리하는 시점

이 잘못되어있었다. 인접한 4방향을 탐색할 때, 그 즉시 방문처리를 해야 의미없이 queue에 offer하지 않게된다

소스

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

public class Main {
	static int N;
	static boolean[][] VISIT;
	static int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 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());
		
		char[][] graphOne = new char[N][N];
		char[][] graphTwo = new char[N][N];
			
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			String temp = st.nextToken();
			for(int j = 0; j < N; j++) {
				graphOne[i][j] = temp.charAt(j);
				if(temp.charAt(j) == 'G') graphTwo[i][j] = 'R';
				else graphTwo[i][j] = temp.charAt(j);
			}
		}
		System.out.println(start(graphOne) + " " + start(graphTwo));
		
	}
	public static int start(char[][] graph) {
		int ret = 0;
		VISIT = new boolean[N][N];
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(!VISIT[i][j]) {
					bfs(i ,j, graph);
					ret++;
				}
			}
		}
		
		return ret;
	}
	public static void bfs(int x, int y, char[][] graph) {
		Queue<Vector> q = new LinkedList<Vector>();
		q.offer(new Vector(x, y));
		VISIT[x][y] = true;
		while(!q.isEmpty()) {
			Vector cur = q.poll();
			
			for(int i = 0; i < dir.length; i++) {
				int nextX = cur.x + dir[i][0];
				int nextY = cur.y + dir[i][1];
				
				if(nextX < 0 || nextX >= N || nextY < 0 || nextY >= N) continue;
				if(!VISIT[nextX][nextY] && graph[nextX][nextY] == graph[cur.x][cur.y]) {
					VISIT[nextX][nextY] = true;
					q.offer(new Vector(nextX, nextY));
				}
			}
		}
	}
}

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