문제 탐색하기
입력 자료 정리
- 입력값 n은 색이 칠해져있는 그리드의 가로 세로 길이다
- 이후 n x n 만큼 들어오는 값은 각 그리드의 원소다.
이때 원소의 타입은 String 또는 char가 될 수 있으며 편의상 char로 받으면 될 것이다
이어서 원소의 종류는 3가지다 R, G, B 이 3가지에 대해서만 생각하면 된다
해결방법 추론
- 문제를 봤을 때, 4방 탐색했을 때, 인접해있는 색을 하나의 색으로 보고
전체 색의 개수를 세는 문제이므로 BFS로 풀면 쉽게 풀 수 있음을 짐작할 수 있다 - 단 이 문제에서 한가지 고려할 것이 있는데, 바로 색약인 사람들에 대한 탐색이다
- 일반 사람들은 입력값 주어진 그대로 BFS 탐색을 해서 개수를 세면 되지만,
색약인 사람들은 R와 G를 같은 값으로 생각해야한다. - 색약인 사람과 정상인 사람을 구분해서 탐색하는 가장 좋은 방법은 둘의 배열을 다르게 하는 것이다
- 간단하게 색약인 사람들이 G를 입력으로 받을 때,
같은 색이라 인식되는 R로 생각하고 입력받으면 된다. - 이후, BFS 탐색에 대해서는 서로 다른 BFS 탐색 메소드를 만들어도 되고,
어차피 둘다 같은 타입의 배열이므로 배열을 파라미터로 둬서,
색약과 정상인 사람의 배열을 모두 처리하는 하나의 BFS 메소드로 해결해도 된다 - 이 문제에서 후자를 선택해서 해결하였다
시간복잡도 계산
- 이번에도 저번과 동일하게 n x n의 연산이 발생한다.
또한 bfs에서 4의 연산이 발생한다 - 따라서 상수시간은 제외하고 생각한다면 시간복잡도는 O(n^2)이 될 것이다
- 시간 제한안에 문제를 해결할 수 있음을 알 수 있다.
- 시간복잡도는 크게 걱정 안 해도 되지만 이 문제는 메모리 제한을 고려해야할 수도 있다
- 128 MB인데 2차원 배열을 2개 쓰기 때문에 자칫하면 메모리 초과상황을 마주할 수도 있다
- 하지만 다행히도 N의 최대 입력은 100이므로 char 타입의 배열을 2개 쓴다고 해도
메모리 초과가 발생하지 않는다 - char타입의 크기는 2Byte 이고, 100 x 100의 크기의 2차원 배열이 있다고 했을 때,
배열 하나당 20,000Byte = 20KB이며, 2개니깐 40KB가 된다. - 따라서 메모리 초과 걱정없이 문제를 해결할 수 있다
코드 설계하기
입력값 상태 관리하기
- 입력값 n은 변수로 관리한다
- char 타입의 2차원 배열을 n x n 크기로 2개 선언한다
- 색약인 사람은 blind, 정상인 사람은 arr에 관리한다
- 이후 입력값을 받을 때, arr인 사람은 그냥 입력값 그대로 받지만,
색약인 사람들은 G라면 R로 바꿔서 저장하고 그 외에는 그냥 그대로 입력값을 받아 관리한다 - 이후 각 BFS 탐색 전에 방문배열을 선언하여, 이전 방문 체크를 초기화해준다
- 각각의 정답 개수를 관리할 변수로 count1, count2를 선언하였다.
이때 각각 정상, 색약이 볼 수 있는 색의 개수다
BFS 설계하기
- 미방문한 지점을 시작지점으로 하여 BFS탐색을 한다
- 다른 bfs탐색과는 다르게 시작지점의 색과,
하나의 메소드로 정상, 색약의 배열을 모두 처리할 수 있도록 현재 탐색하는 배열도 같이 넘겨준다 - 그 외에는 BFS의 4방 탐색을 통해 인접한 모든 색을 방문체크 한다.
이때 시작지점의 색과 같아야하며 미방문했고 인덱스 범위를 벗어나지 말아야 한다
미 방문 지점을 발견할 때마다 그 개수를 세어준다. - 이 과정을 정상에 대해서 먼저 시작해주고, 색약에 대해 먼저 해주면서 그 개수를 세어주면된다
출력값 설계하기
- BFS 탐색을 통해 완성한 색의 개수를 출력하면 정답이된다.
이때 정상이 볼 수 있는 색의 개수를 먼저 출력하고
이어서 색약이 볼 수 있는 색의 개수를 출력해야 한다.
정답 코드
(1회차 시도 성공!)
import java.io.*;
import java.util.*;
public class Main {
static char[][] arr;
static char[][] blind;
static boolean[][] visited;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
arr = new char[n][n];
blind = new char[n][n];
for (int i = 0; i < n; i++) {
String[] input = br.readLine().split("");
for (int j = 0; j < n; j++) {
arr[i][j] = input[j].charAt(0);
if(input[j].charAt(0) == 'G'){
blind[i][j] = 'R';
}else{
blind[i][j] = input[j].charAt(0);
}
}
}
int count1 = 0;
int count2 = 0;
visited = new boolean[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(!visited[i][j]){
bfs(n, i,j, arr[i][j], arr);
count1++;
}
}
}
visited = new boolean[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(!visited[i][j]){
bfs(n, i,j, blind[i][j], blind);
count2++;
}
}
}
bw.write(count1 + " " + count2);
br.close();
bw.close();
}
private static void bfs(int n, int y, int x, char color, char[][] tmp) {
Queue<int[]> q = new LinkedList<>();
q.add(new int[] {y,x});
visited[y][x] = true;
while(!q.isEmpty()){
int[] arr = q.poll();
for (int i = 0; i < 4; i++) {
int ny = arr[0] + dy[i];
int nx = arr[1] + dx[i];
if(ny >= 0 && nx >= 0 && ny < n && nx < n && !visited[ny][nx] && tmp[ny][nx] == color){
visited[ny][nx] = true;
q.add(new int[] {ny,nx});
}
}
}
}
}문제 링크
Software Developer