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);
우와 풀이 완전 고퀄이다 잘보고가요 ^__^