[JavaScript] 백준 10026 적록색약 (JS)

적록색약

📚 문제 설명

R - G - B 중에 하나가 랜덤하게 들어 있는 N * N 크기의 MAP 이 있다.
이 때 몇 개의 구역으로 나누어져 있는지 구하는 문제가 있다.
그런데 만약 적록 색맹인 사람이 있다고 한다면, 이 사람은 총 몇 개의 구역으로 보이는지도 구하라.

예를 들어

아래처럼 MAP이 주어졌을 때, 
RG
GB
적록 색약이 아닌 사람은 4개의 구역.
적록 색약인 사람은 2개의 구역으로 보인다.

👨🏻‍💻 풀이 과정

해당 문제의 경우 DFS나 BFS 어떤 방법을 써도 상관 없지만, 최근에 DFS로 문제를 안풀었던 것 같아서 이번에는 DFS로 풀어보기로 했다.

일단 적록 색약이 아닌 사람이 보는 구역을 계산하는 로직을 확인해보자.

💡 DFS

DFS의 경우 기본적으로 재귀를 사용한다라고 생각하며 코드를 작성하면 생각하기가 편하다.
단, 절대 무한 루프에 빠지지 않게 코드를 작성해야 한다.

따라서 visited 를 이용하여 무한 루프에 빠지지 않게 만들었다.

• DFS 함수 안에서 현재 위치에서 상하좌우로 움직이며, 재귀를 진행.
• visited 를 이용해 이미 왔던 길로 안오게 만들어줌.

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

    let N = parseInt(input.shift());
    const MAP = input.map(v => v.split(''));
	// 정답 배열
    let answer = [0, 0];
	// 상하좌우 움직임
    let dx = [1, -1, 0, 0];
    let dy = [0, 0, 1, -1];

    let visited = new Array(N);

    for (let i = 0; i < visited.length; i++) {
        visited[i] = new Array(N).fill(false);
    }
	// DFS 함수 (현재 위치(x), 현재 위치(y), 찾고자하는 값) 
    const DFS = (x, y, target) => {
      	// 이미 온 위치는 true로 체크
        visited[x][y] = true;
      	// 상하좌우 움직임
        for (let i = 0; i < dx.length; i++) {
            const NextX = x + dx[i];
            const NextY = y + dy[i];
          	// MAP을 벗어나면 넘어감.
            if (NextX < 0 || NextX >= N || NextY < 0 || NextY >= N) continue;
          	// 만약 다음 위치가 MAP을 벗어나지 않고, 이미 갔던 곳이 아니라면.
            if (!visited[NextX][NextY]) {
              	// 다음 위치가 target이라면 재귀.
                if (MAP[NextX][NextY] === target) {
                    DFS(NextX, NextY, target);
                }
            }
        }
    };

그리고 적록 색약을 위한 로직을 만들기 위한 방법이 2가지 정도 생각이 났다.
1. MAP 을 직접 변경하여 구역을 세주는 방법.
2. DFS 함수를 따로 하나 더 만들고, visited 또한 다시 하나 만들어서 진행하는 방법.

그런데 나는 MAP 을 다시 한번 순회하며 값을 바꿔주는 것보다는 visitedForRG 라는 배열을 만들어 주는 것이 시간 복잡도가 더 좋을 것 같아서 해당 방법을 사용하기로 했다.

전체 풀이

    let fs = require("fs");
    let input = fs.readFileSync("./input.text").toString().trim().split('\n');

    // let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let N = parseInt(input.shift());
    const MAP = input.map(v => v.split(''));
    let answer = [0, 0];
    let dx = [1, -1, 0, 0];
    let dy = [0, 0, 1, -1];
	// 적록 색약을 위해 2개의 visited 생성
    let visited = new Array(N);
    let visitedForRG = new Array(N);

    for (let i = 0; i < visited.length; i++) {
        visited[i] = new Array(N).fill(false);
    }
    for (let i = 0; i < visited.length; i++) {
        visitedForRG[i] = new Array(N).fill(false);
    }

	// DFS 함수 (현재 위치(x), 현재 위치(y), 찾고자하는 값) 
    const DFS = (x, y, target) => {
      	// 이미 온 위치는 true로 체크
        visited[x][y] = true;
      	// 상하좌우 움직임
        for (let i = 0; i < dx.length; i++) {
            const NextX = x + dx[i];
            const NextY = y + dy[i];
          	// MAP을 벗어나면 넘어감.
            if (NextX < 0 || NextX >= N || NextY < 0 || NextY >= N) continue;
          	// 만약 다음 위치가 MAP을 벗어나지 않고, 이미 갔던 곳이 아니라면.
            if (!visited[NextX][NextY]) {
              	// 다음 위치가 target이라면 재귀.
                if (MAP[NextX][NextY] === target) {
                    DFS(NextX, NextY, target);
                }
            }
        }
    };
	// 적록 색약을 위한 DFS 로직
    const DfsForRG = (x, y, target) => {
        visitedForRG[x][y] = true;
      	// 만약 R이 들어오면 G를 저장.
      	// 만약 G가 들어오면 R을 저장.
        let RorG = 'B';
        if (target !== 'B') {
            RorG = target === 'R' ? 'G' : 'R';
        }
      	// 상하좌우 움직임.
        for (let i = 0; i < dx.length; i++) {
            const NextX = x + dx[i];
            const NextY = y + dy[i];
            if (NextX < 0 || NextX >= N || NextY < 0 || NextY >= N) continue;
            if (!visitedForRG[NextX][NextY]) {
              	// 적록 색약을 위해 R 혹은 G 로 이동 가능하도록. 
              	// 하지만 B이면 B로만 이동.
                if (MAP[NextX][NextY] === target || MAP[NextX][NextY] === RorG) {
                    DfsForRG(NextX, NextY, target);
                }
            }
        }

    };

	// 전체 맵을 돌며 확인.
    const solution = () => {
        for (let i = 0; i < N; i++) {
            for (let j = 0; j < N; j++) {
                if (!visited[i][j]) {
                    DFS(i, j, MAP[i][j]);
                    answer[0]++;
                }
                if (!visitedForRG[i][j]) {
                    DfsForRG(i, j, MAP[i][j]);
                    answer[1]++;
                }
            }
        }
    };

    solution();
    console.log(answer.join(' '));

🧐 후기

오랜만에 DFS 문제를 풀다보니, 무한 루프에 빠지지 않기 위해 코드를 작성하며 중간중간 고민을 좀 많이 했던 것 같다.