백준 10026 자바스크립트

문제

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

10026번: 적록색약

접근

기본적인 그래프 탐색 문제. 

적록색맹인 경우와 적록색맹이 아닌 경우로 visited 배열을 따로 만들어 계산한다.

풀이

참조(https://zzang9ha.tistory.com/227)

 

시도1: 우선 notRBG부터 구하기 

expected: 4

result: 2

debugging: visited 의 문제였다.

const wrongVisited = Array(N).fill(Array(N).fill(false));

  const rightVisited = Array.from(Array(N), () => Array(N).fill(false));

이유는 모르겠지만, x=0, y=0 일때, visited[x][y] = true 를 진행했을 때 전자는 이렇게 y=0 부분이 전부 true 로 바뀐 걸 볼 수 있다. 

후자는 예상했던 것처럼 딱 visitied[0][0]부분만 true 로 표시된 걸 알 수 있다.

근데 웃긴건 전자 후자 모두 맨 처음 상태 콘솔찍어보면 같은 모양이다. 

 이유는 모르겠지만, 이런 개떡같은 이유로 40분을 날린 것이 원통하다. 우선은 문제 풀이에 필요한 기본 논리는 파악한 것에 만족하고 넘어가자. 앞으로는 절대 visited 후자로만 쓸 것이다.

const solution = (input) => {
  const N = +input.shift();
  const graph = input.map((v) => v.split(""));

  const dx = [0, 1, 0, -1];
  const dy = [1, 0, -1, 0];
  const visited = Array(N).fill(Array(N).fill(false));
  let cnt = 0;

  const isInRange = (nx, ny) => {
    if (nx >= 0 && ny >= 0 && nx < N && ny < N) return true;
    return false;
  };

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
     
     const dfs = (x, y) => {
        visited[x][y] = true;

        for (let k = 0; k < dx.length; k++) {
          const nx = x + dx[k];
          const ny = y + dy[k];

          if (
            isInRange(nx, ny) &&
            !visited[nx][ny] &&
            graph[nx][ny] === graph[x][y]
          ) {
            dfs(nx, ny);
          }
        }
      };

      if (!visited[i][j]) {
        dfs(i, j);
        cnt++;
      }
    }
  }
  return cnt;
};