[Baekjoon (Node.js)] 10026번 적록색약

📄 문제

문제 사진

입출력 예제

---

📝 나의 통과 풀이

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
const N = Number(input[0]);

let first = 0;
let second = 0;
let board = Array.from(new Array(N));
board.forEach((item, index) => {
  let target = input.slice(1)[index].replace("\r", "");
  board[index] = target.split("");
});

let visit = Array(N)
  .fill(0)
  .map(() => Array(N).fill(0));

let dx = [0, 0, 1, -1];
let dy = [1, -1, 0, 0];

let queue = [];
function BFS(row, col) {
  queue.push([row, col]);
  visit[row][col] = 1;
  if (queue.length !== 0) {
    for (let i = 0; i < queue.length; i++) {
      let target = queue.shift();
      for (let j = 0; j < dx.length; j++) {
        let newX = target[0] + dx[j];
        let newY = target[1] + dy[j];
        if (newX >= 0 && newX < N && newY >= 0 && newY < N) {
          let currentValue = board[target[0]][target[1]];
          if (visit[newX][newY] === 0 && currentValue === board[newX][newY]) {
            visit[newX][newY] = 1;
            BFS(newX, newY);
          }
        }
      }
    }
  }
}

for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    if (!visit[i][j]) {
      BFS(i, j);
      first++;
    }
  }
  for (let j = 0; j < N; j++) {
    if (board[i][j] === "R") {
      board[i][j] = "G";
    }
  }
}

for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    visit[i][j] = 0;
  }
}
for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    if (!visit[i][j]) {
      BFS(i, j);
      second++;
    }
  }
}
console.log(first, second);

쉬운게 없다...

---

⌨ 접근법

1. 입력을 잘라서 계속해서 반복문을 돌릴 N과, RGB 보드 array , 탐색 체크용 visit array를 만든다.

2. 위, 아래, 오른쪽, 왼쪽 총 4방향을 탐색하기 위해 두개를 묶어서 쓸 x와 y array 두 개를 만든다.

3. 문제에서 구역의 수를 구해야 하므로 인접 구역 확인을 위해 빈 queue array를 만들어 둔다.

4. bfs 함수를 만든다 => 기능설명

4-1. 이 함수는 row, col 즉 x와 y를 인자로 받는다.

4-2. 인자를 받으면 queue에 바로 넣어주고 그 좌표인 visit를 1로 바꿔서 왔다고 표시해준다. ex) queue = [0,0] || visit [0,0,]  = 1

4-3. queue를 기준으로 4방향씩 쭉쭉 연결되어 있는 곳을 탐색할 거니까 만약 queue에 인자가 있다면 반복문을 실행한다.

4-4. queue의 가장 처음 놈이 target이다.(ex) target = [0,0]) target한테 아까 정한 4방향 좌표를 하나씩 넣어보면서 board밖을 나가는지 체크하고 나가지 않는다면 현재 그 위치가 0이면서, (방문한 적 없으면서) 탐색하고자 하는 방향의 값과, 현재의 값을 비교해서 같으면 현재 위치를 1로 방문 표시해주고 새로운 위치 좌표로 bfs를 다시 돌린다.

=> 이런 루프로 돌면 시작 좌표의 값과 붙어있는 놈들은 다 체크가 되고 끊기는 순간 bfs 종료

5. 이걸 전 좌표 다 돌려주는데 방문한 적이 없을 때만 bfs 함수가 실행되게 한다. 

=> 0,0부터 시작해서 연결된 놈들 다 방문 표시 => 다른 좌표들을 탐색하는데 방문된 곳은 bfs 미실행 즉 이미 한 구역

6. 이렇게 구역의 수를 구해서 first에 카운트해주고 적록색약인 분을 위해 빨강과 초록의 값을 통일시켜 준다.

7. 이 루프가 끝나면 visit를 초기화해주고 다시 bfs를 돌려주면 합쳐진 구역이 카운트되고

8. 적록색약이 아닌 분 first와 적록색약인 분 second를 같이 출력해줘서 성공

---

😤 스토리

- 틀렸습니다! 신나게 떴던 포인트 -

1. 처음엔 visit를 초기화하는 부분을 적록색약인 분과 같은 for문에 넣어서 틀렸습니다가 떴다. (아직도 이유를 모르겠다)

2. bfs문 안에 queue.length 만큼 돌리라는 부분이 있는데 이 부분을 queue.forEach()로 계속 돌리고 있었다. (4,4 탐색 안됨) => 완전한 루프가 아니었다.

3. console.log(first +''+second)로 출력했는데 에러 뜬다. (아직도 이유를 모르겠다.)

 

- 루프 짜는데 어려워서 다른 분의 파이썬 코드를 참고해서 구현했다. -

1. 팀원들과 트리 탐색 위주로 하다가 2차원 배열 나오니까 멘붕 와서 엄청 헤맸던 것 같다.

2. 백준에 질문 검색 탭은 진짜 한줄기 빛이다.. 반례도 가끔 있어서 확인 가능하고, 언어는 다르지만 다른 분의 로직을 보면서 참고하니 공부하기에 더 좋은 것 같다. (node.js는 진짜 푸는 사람이 없다.)

---

📚 문제 링크

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

10026번: 적록색약