본문 바로가기
자료구조&알고리즘/DFS BFS

[백준] dfs - 10026번 적록색약 (Java)

by _din 2021. 5. 23.

문제링크

 

10026번: 적록색약

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)

www.acmicpc.net

 

접근한 방법

  • 구역을 구하는 문제이므로
    dfs

 


풀이방법

두 가지 경우를 나누어 탐색을 수행한다.

1) 적록색약이 아닌 경우 : R, G, B 구역

2) 적록색약인 경우 : R 또는 G, B 구역

 

1. 특정한 지점의 주변 상, 좌, 하, 우를 살펴본 뒤에 주변 지점 중에서 탐색하는 지점의 문자가 R, G, B중 적록색약일 경우와 아닌 경우에 따라 (아래 참조) 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
   - 적록색약이 아닌 사람일 경우 현재 탐색중인 문자와 같을 때(e.g. 현재 탐색중인 문자가 R이라면 R만 탐색)만 탐색
   - 적록색약일 경우 현재 탐색중인 문자가 R이거나 G라면 R과 G인 경우도 포함하여 탐색
2. 방문한 지점 에서 다시 상, 좌, 하, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.
   방문시마다 요소의 수를 더해준다.
3. 1~2번의 과정을 모든 노드에 반복

 


소스코드 작성 방법

  • 맵의 크기(n)를 전역 필드로 선언한다.
  • 그림의 정보(map), 방문 여부(visitied1, visited2)는 두가지 경우를 나누어 전역 필드로 선언한다.
  • 각 영역의 개수(count1, count2)를 전역 필드로 선언한다.
  • 방향 배열 dx, dy로 상 좌 하 우 움직임을 저장한다.
  • dfs 메소드를 적록색약인 경우와 적록색약이 아닐 경우 2가지를 선언한다.
  • dfs 메소드 공통으로 인자를 노드 번호(curR, curC)와 현재 탐색하고 있는 문자(c)를 받는다.
    • vistied[curR][curC] = true로 하여 방문 처리
    • 방문할 때 마다 count++하여 집의 개수를 추가한다.
    • nextR, nextC를 for문 안에 선언하여 현재 위치에서 상 좌 하 우 위치를 탐색한다.
      • nextR은 curR + dx[dir]
        nextC는 curC + dx[dir] 로 상 좌 하 우 값을 선언해준다.
      • 상 좌 하 우 위치 이동 시 n*n배열의 크기보다 크면 continue하여 넘어간다.
  • 1) 적록색약이 아닌 경우 - 현재 탐색중인 문자와 같은 값을 가져야 탐색 진행
    • map[nextR][nextC] = c 이고 visited[nextR][nextC] = false로 아직 방문하지 않았다면
      dfs 메소드를 재귀적으로 호출하여 방문수행
  • 2) 적록색약인 경우 - 현재 탐색중인 문자가 R이나 G라면 R과 G 값을 가진 경우도, B라면 B값을 가진 경우만 탐색 진행
    • 탐색중인 값이 R이나 G일 때)
      • map[nextR][nextC] = c 이고 visited[nextR][nextC] = false로 아직 방문하지 않았다면
        dfs 메소드를 재귀적으로 호출하여 방문수행
    • 탐색중인 값이 B일 때)
      • map[nextR][nextC] = c 이고 visited[nextR][nextC] = false로 아직 방문하지 않았다면
        dfs 메소드를 재귀적으로 호출하여 방문수행
  • solution 메소드에서 (0,0) 노드부터 (n-1,n-1)노드까지 탐색을 수행한다.
    • dfs 메소드가 끝날때마다 count를 ++ 해준다.

 

소스코드

package baekjoon.dfs_bfs;
import java.io.*;

public class Q_10026_ColorWeakness_20210523 {
    public static int n;
    public static char[][] map;
    public static boolean[][] visited1; // 적록색약이 아닌 사람 방문 체크
    public static boolean[][] visited2; // 적록색약인 사람 방분 체크
    public static int count1, count2; // 결과
    // 상좌하우
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, -1, 0, 1};

    public static void solution() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(!visited1[i][j]){
                    dfs1(i, j, map[i][j]);
                    count1++;
                }
                if(!visited2[i][j]){
                    dfs2(i, j, map[i][j]);
                    count2++;
                }
            }
        }
    }

    // 적록색약이 아닌 사람 체크 - R, G, B 구역
    public static void dfs1(int curR, int curC, char c){
        visited1[curR][curC] = true;

        for (int i = 0; i < 4; i++) {
            int nextR = curR + dx[i];
            int nextC = curC + dy[i];

            if(nextR <0 || nextC <0 || nextR >=n || nextC >=n) continue;
            else if(map[nextR][nextC] == c && !visited1[nextR][nextC]){
                dfs1(nextR, nextC, c);
            }

        }

    }

    // 적록색약인 사람 체크 - RG, B 구역
    public static void dfs2(int curR, int curC, char c){
        visited2[curR][curC] = true;

        for (int i = 0; i < 4; i++) {
            int nextR = curR + dx[i];
            int nextC = curC + dy[i];

            if(nextR <0 || nextC <0 || nextR >=n || nextC >=n) continue;
            else{
                if(c == 'B'){
                    if(map[nextR][nextC] == 'B' && !visited2[nextR][nextC])
                        dfs2(nextR, nextC, c);
                } else {
                    if((map[nextR][nextC] == 'R' || map[nextR][nextC] == 'G') && !visited2[nextR][nextC])
                        dfs2(nextR, nextC, c);
                }
            }
        }

    }

    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];
        visited1 = new boolean[n][n];
        visited2 = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < n; j++) {
                map[i][j] = str.charAt(j);
            }
        }

        solution();
        bw.write(count1+" "+count2);

        br.close();
        bw.close();

    }
}
반응형

댓글