[BOJ] 10026.적록색약.java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못하므로

입력받을 때 그냥 G일 경우 R로 저장을 했다.

visited[][] 배열을 따로 사용하지 않고 방문한 좌표는 X로 수정해주었다.

그래서 방문하지 않은 좌표 'X'인 경우 pass

dfs에서는

들어오자마자 방문처리를 해주고,

탐색 과정에서 범위를 넘어갈 경우, 이미 방문한 경우, 색상이 있지만 나와 다른 색상일 경우

continue를 해주고 이 모든 조건을 통과했을 경우

다시 탐색 좌표로 dfs를 호출해주었다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter;   public class BOJ10026 {       static int N;     static char map[][], map2[][];     static int dx[] = { -1, 1, 0, 0 };     static int dy[] = { 0, 0, -1, 1 };       // 정상     public static void dfs(int x, int y, char col) {         // 방문 처리         map[x][y] = 'X';           for (int d = 0; d < 4; d++) {             int xx = x + dx[d];             int yy = y + dy[d];             // 범위를 넘어가면 pass             if (xx < 0 || yy < 0 || xx >= N || yy >= N) continue;             // 이미 방문한 곳이면 pass             if (map[xx][yy] == 'X') continue;             // 색이 있는데 다른 색이면 pass             if (col != map[xx][yy]) continue;             dfs(xx, yy, map[xx][yy]);         }     }       // 적록색약     public static void dfs2(int x, int y, char col) {         // 방문 처리         map2[x][y] = 'X';           for (int d = 0; d < 4; d++) {             int xx = x + dx[d];             int yy = y + dy[d];             // 범위를 넘어가면 pass             if (xx < 0 || yy < 0 || xx >= N || yy >= N) continue;             // 이미 방문한 곳이면 pass             if (map2[xx][yy] == 'X') continue;             // 색이 있는데 다른 색이면 pass             if (col != map2[xx][yy]) continue;             dfs2(xx, yy, map2[xx][yy]);         }     }       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));           N = Integer.parseInt(br.readLine());         map = new char[N][N];    // 정상         map2 = new char[N][N];    // 적록색약         for (int i = 0; i < N; i++) {             String in = br.readLine();             for (int j = 0; j < N; j++) {                 // 정상                 map[i][j] = in.charAt(j);                  // 적록색약: 빨간색과 초록색의 차이를 거의 느끼지 못한다 (G일 경우 R로 저장)                 if (in.charAt(j) == 'G')  map2[i][j] = 'R';                  else map2[i][j] = in.charAt(j);              }         }           int cnt = 0; // 정상         int cnt2 = 0;    // 적록색약         for (int i = 0; i < N; i++) {             for (int j = 0; j < N; j++) {                 // 정상 : 방문하지 않은 곳이면                 if (map[i][j] != 'X') {                     dfs(i, j, map[i][j]);                     cnt++;                 }                 // 적록색약 : 방문하지 않은 곳이면                 if (map2[i][j] != 'X') {                     dfs2(i, j, map2[i][j]);                     cnt2++;                 }             }         }           System.out.println(cnt + " " + cnt2);     } }   Colored by Color Scripter

cs

#. Other Code