배운 것, 유의할 것
그래프 풀이 시 방문 체크 배열 생성
평소에 그래프 문제에서 방문 여부를 체크할 때 이중 배열을 만드는 경우가 많은데, 항상 수동으로 만들어 줬었다.
방문 여부를 체크하는 이중 배열은 그래프의 배열과 사이즈가 같기 때문에 map 메소드를 활용해서 간단하게 만들어봤는데 잘 적용되었다. 기억할 것.
// 이중배열의 그래프가 있다면
const board = [[1, 2], [3, 4]];
// 아래와 같이 방문 여부를 나타내는 이중 배열을 만들 수 있다.
const visited = board.map(a=>a.map(b=>false));
배열에서 함수를 담고 꺼내쓰기…?
이번문제는 한칸 이동이 아니라 상하좌우 네 방향으로 쭉 이동하면서 장애물이나 벽을 만나는지를 체크해줘야하고, row 방향인지 col 방향인지에 따라 제어해줘야하는 변수가 달라서 어떻게 만져야할지 고민을 많이했다.
비효율적인 방법인지는 모르겠지만, 네 방향으로 가면서 도착지를 구하는 함수를 각각 만들어주고 order라는 배열에 담고 bfs 함수에서 순회할 때 아래와 같이 꺼내써봤다.
작성하는 함수의 코드가 너무 방대해지지 않도록 필요한 기능을 모듈화 하고, 반복문으로 꺼내다쓴 경험.
// bfs 함수에서 필요로 하는 네 가지 기능
function toLeft(..){
...
}
function toRight(..){
...
}
function toTop(..){
...
}
function toBottom(..){
...
}
// 이 네 함수를 배열에 담는다
const order = [toLeft, toRigth, toTop, toBottom];
// 반복문을 통해 꺼내다 쓰기
for(let i = 0; i < order.length; i++){
const dest = order[i](row,col,cnt);
...
}
정답코드
function solution(board) {
let answer = -1;
// board를 2차원 배열로 수정
board = board.map(v=>v.split(''));
// 방문여부 기록할 배열
const visited = board.map(a=>a.map(b=>false));
// 'G',' D'와 '.'를 변수화해서 사용
const R = 'R';
const G = 'G';
const D = 'D';
const dot = '.';
// 좌, 우, 상, 하로 이동하는 함수들
function toLeft(row, col, cnt){
// 현재 col에서부터 0까지
for(let i = col; i >= 0; i--){
// 'D'를 만나거나 '.'을 만나는 경우 멈추는데
if(board[row][i] === D){
// D를 만나면 그 전에 정지
return [row, i + 1, cnt + 1];
} else if(i === 0){
// 벽에 도착하면 그 자리에 정지
return [row, i, cnt + 1];
}
}
}
function toRight(row, col, cnt){
for(let i = col; i < board[0].length; i++){
if(board[row][i] === D){
return [row, i - 1, cnt + 1];
} else if(i === board[0].length - 1){
return [row, i, cnt + 1];
}
}
}
function toTop(row, col, cnt){
for(let i = row; i >= 0; i--){
if(board[i][col] === D){
return [i + 1, col, cnt + 1];
} else if(i === 0){
return [i, col, cnt + 1];
}
}
}
function toBottom(row, col, cnt){
for(let i = row; i < board.length; i++){
if(board[i][col] === D){
return [i - 1, col, cnt + 1];
} else if(i === board.length - 1){
return [i, col, cnt + 1];
}
}
}
// 네 방향 다 둘러보기 위한 명령을 배열에 담음
const order = [toLeft, toRight, toTop, toBottom]
function bfs(x,y){
// 몇 번 만에 방문했는지 체크
let count = 0;
// 큐에 넣고
const q = [[x,y,count]];
// 방문처리
visited[x][y] = true;
while(q.length){
const [row, col, cnt] = q.shift();
for(let i = 0; i < 4; i++){
const [newR, newC, newCnt] = order[i](row, col, cnt);
// 방문한 적이 없고,
if(!visited[newR][newC]){
// 목적지라면 newCnt 반환
if(board[newR][newC] === G) {
return answer = newCnt;
}
// 목적지 아니라면 큐에 넣고 방문처리
q.push([newR, newC, newCnt]);
visited[newR][newC] = true;
}
}
}
}
for(let i = 0; i < board.length; i++){
for(let j = 0; j < board[0].length; j++){
if(board[i][j] === R) bfs(i,j);
}
}
return answer;
}
'알고리즘 문제풀이' 카테고리의 다른 글
프로그래머스 level 2 - 두 큐 합 같게 만들기(Javascript) (0) | 2023.11.07 |
---|---|
프로그래머스 level 2 - 마법의 엘리베이터(Javascript) (0) | 2023.11.06 |
프로그래머스 level 3 - 정수 삼각형(Javascript) (1) | 2023.10.28 |
프로그래머스 - 게임 맵 최단거리(DFS, BFS) (0) | 2023.09.05 |
프로그래머스 - 카펫(완전탐색) (0) | 2023.09.02 |