[BAEKJOON_10026 - JAVA] 적록색약_V2

문제

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

10026번: 적록색약

 

 

풀이

• 기존에 풀었지만 알고리즘 스터디 문제에 있어서 재풀이.
• 기존에는 map을 적록색약 전용으로 복사를 해서 풀었지만, 이번에는 하나의 메소드에 적록색약 여부를 전달.
• map의 크기가 N<100 이하이기 때문에 복사를 하는 것이 더 효율적으로 보이지만, N의 크기가 커질수록 이번 풀이가 더 효율적일 것으로 생각되어 도전.
• 탐색 방법도 변경해보았다.(기존 : dfs → 현재 : bfs) 

 

 

기존 풀이

기존의 코드가 백준의 testcase에서는 더 높은 효율을 보입니다.

2020/06/27 - [JAVA/[JAVA - BAEKJOON] 알고리즘] - [BAEKJOON_10026 - JAVA] 적록색약

[BAEKJOON_10026 - JAVA] 적록색약

 

 

과정

1. map을 공유, 방문관리용 visit배열 생성.
2. search(행, 열, 적록색약이 아닌 경우) 로 호출
3. 좌표 정보를 가진 Pos 객체로 Queue 생성
4. 4방 탐색을 하며, 색약 여부에 따른 조건문 분할
5. 배열의 범위 검사 && 방문 검사 && 같은 색(적록색약의 경우 적록은 같다)인 경우를 검사 
6. 첫번째 호출 종료
7. visit 배열 재생성 후, search(행, 열, 적록색약인 경우) 로 호출
8. 이후의 과정은 3~6번의 흐름과 같다.

 

 

알고리즘 지식

• DFS or BFS

 

 

JAVA코드

package BaekJoon_2020_12_23__30;

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

/**
 * @packageName : BaekJoon_2020_12_23__30
 * @fileName : BJ_10026_적록색약.java
 * @author : Mingeon
 * @date : 2020. 12. 27.
 * @language : JAVA
 * @classification :
 * @time_limit : 1sec
 * @required_time : 10:49 ~ 11:28
 * @submissions : 1
 * @description
 */

public class BJ_10026_적록색약 {

	static int N; // map의 크기
	static char[][] map; // map 정보
	static boolean[][] visit; // 방문관리

	// 4방 탐색
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new char[N][N];

		for (int i = 0; i < N; i++) {
			map[i] = br.readLine().toCharArray();
		}

		// 적록색약이 아닌 사람
		int ret1 = 0;
		visit = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!visit[i][j]) {
					search(i, j, false);
					ret1++;
				}
			}
		}

		// 적록색약인 사람
		int ret2 = 0;
		visit = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!visit[i][j]) {
					search(i, j, true);
					ret2++;
				}
			}
		}

		System.out.println(ret1 + " " + ret2);
		br.close();

	}

	// 행, 열, 적록색약 여부
	private static void search(int r, int c, boolean visualType) {
		Queue<Pos> q = new LinkedList<Pos>();
		q.add(new Pos(r, c));
		visit[r][c] = true;
		char color = map[r][c];

		while (!q.isEmpty()) {
			int row = q.peek().row;
			int col = q.poll().col;

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

				int nextRow = row + dy[d];
				int nextCol = col + dx[d];

				// 색약이 아닌 사람
				if (!visualType) {
					// 범위 검사 && 방문 검사 && 같은 색인 경우
					if (isIn(nextRow, nextCol) && !visit[nextRow][nextCol] && color == map[nextRow][nextCol]) {
						visit[nextRow][nextCol] = true;
						q.add(new Pos(nextRow, nextCol));
					}
				}

				// 색약인 사람
				else {
					// 범위 검사 && 방문 검사
					if (isIn(nextRow, nextCol) && !visit[nextRow][nextCol]) {
						// 적녹색 구분을 없앤다.
						if (color == 'G' || color == 'R') {
							if (map[nextRow][nextCol] == 'G' || map[nextRow][nextCol] == 'R') {
								visit[nextRow][nextCol] = true;
								q.add(new Pos(nextRow, nextCol));
							}
						}
						// 적녹색 이외의 색 구분
						else if (color == map[nextRow][nextCol]) {
							visit[nextRow][nextCol] = true;
							q.add(new Pos(nextRow, nextCol));
						}
					}
				}
			}
		}
	}

	// 범위 검사
	private static boolean isIn(int row, int col) {
		if (row < 0 || row >= N || col < 0 || col >= N) {
			return false;
		}
		return true;
	}

}

// 좌표를 담을 class
class Pos {
	int row;
	int col;

	public Pos(int row, int col) {
		this.row = row;
		this.col = col;
	}

}