mingssssss

1. 문제

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

2. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	static ArrayList<ArrayList<Character>> list;
	static ArrayList<ArrayList<Character>> list2;
	static boolean[][] visited;
	static boolean[][] visited2;
	static char alpha;
	static char alpha2;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		list = new ArrayList<>();
		list2 = new ArrayList<>();

		int N = Integer.parseInt(br.readLine());
		visited = new boolean[N][N];
		visited2 = new boolean[N][N];

		for (int i = 0; i < N; i++) {
			list.add(new ArrayList<>());
			list2.add(new ArrayList<>());
		}

		for (int i = 0; i < N; i++) {
			char[] cc = br.readLine().toCharArray();
			for (int j = 0; j < cc.length; j++) {
				list.get(i).add(cc[j]);
				if (cc[j] == 'G') {
					list2.get(i).add('R');
				} else {
					list2.get(i).add(cc[j]);
				}
			}
		}
		// 입력 종료

		int answer1 = 0;
		int answer2 = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {

				if (visited[i][j] == false) {
					alpha = list.get(i).get(j);
					bfs(i, j, alpha, N, list, visited);
					answer1++;
				}

				if (visited2[i][j] == false) {
					alpha2 = list2.get(i).get(j);
					bfs2(i, j, alpha2, N, list2, visited2);
					answer2++;
				}
			}
		}

		System.out.println(answer1 + " " + answer2);

//		// 출력
//		for (int i = 0; i < N; i++) {
//			for (int j = 0; j < N; j++) {
//				System.out.printf("%s ", list2.get(i).get(j));
//			}
//			System.out.println();
//		}

	}

	private static void bfs(int r, int c, char alpha, int N, ArrayList<ArrayList<Character>> list,
			boolean[][] visited) {

		Queue<int[]> q = new LinkedList<>();

		q.add(new int[] { r, c });
		visited[r][c] = true;

		while (!q.isEmpty()) {

			int[] now = q.poll();

			for (int i = 0; i < 4; i++) {

				int nextX = now[0] + dx[i];
				int nextY = now[1] + dy[i];

				if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) {
					continue;
				}

				if (visited[nextX][nextY] == true || list.get(nextX).get(nextY) != alpha) {
					continue;
				}

				visited[nextX][nextY] = true;
				q.add(new int[] { nextX, nextY });

			}
		}

	}

	private static void bfs2(int r, int c, char alpha2, int N, ArrayList<ArrayList<Character>> list2,
			boolean[][] visited2) {

		Queue<int[]> q2 = new LinkedList<>();

		q2.add(new int[] { r, c });
		visited2[r][c] = true;

		while (!q2.isEmpty()) {

			int[] now2 = q2.poll();

			for (int i = 0; i < 4; i++) {

				int nextX = now2[0] + dx[i];
				int nextY = now2[1] + dy[i];

				if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) {
					continue;
				}

				if (visited2[nextX][nextY] == true || list2.get(nextX).get(nextY) != alpha2) {
					continue;
				}

				visited2[nextX][nextY] = true;
				q2.add(new int[] { nextX, nextY });

			}
		}

	}

}

3. 리뷰

전형적인 bfs 문제다. 초기 list를 bfs 돌려주고, 적록색약의 경우를 따로 분리해서

bfs를 돌려줬다.

리스트를 두 개 만들어서 적록색약 리스트는 R을 G로 바꾸어서 list를 입력했다.

메모리와 시간 둘 다 나쁘지 않아서 적당한 풀이였던 것 같다.

물론 방문함수를 하나로 줄일 수도 있었을 것 같다..