[BOJ] 적록색약 | BFS

Problem | 적록색약

🙄 문제 풀기 전, 활용 문제

7*7 격자판 미로를 탈출하는 최단경로의 길이를 출력하는 프로그램을 출력하는 프로그램을 작성하세요. 경로의 길이는 출발점에서 도착점까지 가는데 이동한 횟수를 의미한다. 격자판 1은 벽이고 0은 도로다. 격자판의 움직임은 상화좌우로만 움직인다.

입력 예제 |
[[0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1, 0], [0, 0, 0, 1, 0, 0, 0],[1, 1, 0, 1, 0, 1, 1],
[1, 1, 0, 1, 0, 0, 0], [1, 0, 0, 0, 1, 0, 0], [1, 0, 1, 0, 0, 0, 0]]

출력 예제 |
12

function solution(board){  
    let answer=0;
    let n=board.length;
    let dx=[-1, 0, 1, 0];
    let dy=[0, 1, 0, -1];
    let dist=Array.from(Array(7), ()=>Array(7).fill(0));
    function BFS(x, y){
        let queue=[]; 
        queue.push([x, y]);
        board[x][y]=1;
        while(queue.length){
            let curr=queue.shift();
            for(let j=0; j<4; j++){
                let nx=curr[0]+dx[j];
                let ny=curr[1]+dy[j];
                if(nx>=0 && nx<7 && ny>=0 && ny<7 && board[nx][ny]==0){
                    board[nx][ny]=1;
                    dist[nx][ny]=dist[curr[0]][curr[1]]+1;
                    queue.push([nx, ny]);
                }
            }   
        }
    }
    BFS(0, 0);
    console.log(dist);
    if(dist[6][6]===0) return -1;
    else answer=dist[6][6];
    return answer;
}
let arr=[[0, 0, 0, 0, 0, 0, 0], 
         [0, 1, 1, 1, 1, 1, 0],
         [0, 0, 0, 1, 0, 0, 0], 
         [1, 1, 0, 1, 0, 1, 1], 
         [1, 1, 0, 1, 0, 0, 0], 
         [1, 0, 0, 0, 1, 0, 0], 
         [1, 0, 1, 0, 0, 0, 0]];

console.log(solution(arr));

🍀 그래서 적록색약 풀이 !

전체 코드

const { log } = require("console");

let input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
let n = Number(input[0]);
let arr = new Array(n);
let cnt_able = (cnt_disable = 0);
for (let i = 0; i < arr.length; i++) {
  arr[i] = input[i + 1].split("");
}
let check = new Array(n);
for (let i = 0; i < check.length; i++) {
  check[i] = new Array(n).fill(0);
}

// arr : 담겨있는 배열

// <--------- 풀이 시작 ---------->
let dx = [-1, 0, 1, 0];
let dy = [0, 1, 0, -1];
function BFS(x, y) {
  let queue = [];
  queue.push([x, y]);
  check[x][y] = 1;
  while (queue.length) {
    let current = queue.shift();
    for (let i = 0; i < 4; i++) {
      let nx = current[0] + dx[i];
      let ny = current[1] + dy[i];
      if (nx >= 0 && nx < n && ny >= 0 && ny < n && check[nx][ny] === 0) {
        if (arr[current[0]][current[1]] === arr[nx][ny]) {
          check[nx][ny] = 1;
          queue.push([nx, ny]);
        }
      }
    }
  }
}

let count_grb=0;
for(let i=0;i<n;i++){
  for(let j=0;j<n;j++){
    if(!check[i][j]){
      BFS(i,j);
      count_grb++;
    }
  }
}
// 방문 안한 사람

// 적록 색약인 사람의 배열 다시 정렬

for(let i=0;i<n;i++){
  for(let j=0;j<n;j++){
    if(arr[i][j]==="G") arr[i][j]="R";
    check[i][j]=0;
    // 배열 변경시켜주면서 체크 배열 초기화
  }
}

let count_gr=0;
for(let i=0;i<n;i++){
  for(let j=0;j<n;j++){
    if(!check[i][j]){
      BFS(i,j);
      count_gr++;
    }
  }
}

console.log(count_grb, count_gr);