정답 코드
function solution(maze) {
let answer = [];
const n = maze.length;
const m = maze[0].length;
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];
let bs;
let rs;
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
switch(maze[i][j]) {
case 2:
bs = [i, j];
break;
case 1:
rs = [i, j];
break;
}
}
}
const visited = Array.from({ length: 2 }, () =>
Array.from({ length: n }, () =>
Array.from({ length: m}, () => 0)
)
);
visited[0][bs[0]][bs[1]] = 1;
visited[1][rs[0]][rs[1]] = 1;
function check(a, b, ball) {
return (0 <= a && a < n && 0 <= b && b < m) && visited[ball][a][b] === 0
}
function dfs(x, y, depth) {
let [bx, by] = x;
let [rx, ry] = y;
if (maze[bx][by] === 4 && maze[rx][ry] === 3) {
answer.push(depth)
return
} else if (maze[bx][by] !== 4 && maze[rx][ry] !== 3) {
for (let i = 0; i < 4; i++) {
let nbx = bx + dx[i];
let nby = by + dy[i];
if (check(nbx, nby, 0) && maze[nbx][nby] !== 5) {
for (let d = 0; d < 4; d++) {
let nrx = rx + dx[d];
let nry = ry + dy[d];
if (check(nrx, nry, 1) && !(nbx === nrx && nby === nry) && maze[nrx][nry] !== 5) {
if (!((nbx === rx && nby === ry) && (bx === nrx && by === nry))) {
visited[0][nbx][nby] = 1
visited[1][nrx][nry] = 1
dfs([nbx, nby], [nrx, nry], depth + 1)
visited[0][nbx][nby] = 0
visited[1][nrx][nry] = 0
}
}
}
}
}
} else if (maze[bx][by] !== 4 && maze[rx][ry] === 3) {
for (let i = 0; i < 4; i++) {
let nbx = bx + dx[i];
let nby = by + dy[i];
if (check(nbx, nby, 0) && !(nbx === rx && nby === ry) && maze[nbx][nby] !== 5) {
visited[0][nbx][nby] = 1
dfs([nbx, nby], [rx, ry], depth + 1)
visited[0][nbx][nby] = 0
}
}
} else if (maze[bx][by] === 4 && maze[rx][ry] !== 3) {
for (let i = 0; i < 4; i++) {
let nrx = rx + dx[i];
let nry = ry + dy[i];
if (check(nrx, nry, 1) && !(bx === nrx && by === nry) && maze[nrx][nry] !== 5) {
visited[1][nrx][nry] = 1
dfs([bx, by], [nrx, nry], depth + 1)
visited[1][nrx][nry] = 0
}
}
};
};
dfs(bs, rs, 0);
if (answer.length === 0) {
return 0
} else {
return Math.min(...answer)
}
};풀이 방향
그래프 탐색이므로 DFS 또는 BFS로 접근해봅시당
보통 최소 횟수 탐색의 경우 BFS로 푸는 것이 더 좋은 접근입니다
BFS는 탐색 완료 조건을 만나면 그곳에서 바로 함수를 종료하면 결과는 항상 최소 횟수이기 때문이죠
하지만 이런 문제의 경우 BFS로 푼다면 각 경우에 대해서 이전 상황을 알기 위해 visited 배열을 계속해서 가지고 다녀야합니다. -> 메모리 측면에서 굉장히 비효율적입니다.
그래서 visited는 전역에서 한 번 만 선언 및 할당하고 하나의 visited를 계속 재사용 하는 방법을 사용해야합니다.
-> 재귀함수로 DFS 방법으로 구현해야겠죵
풀이 설명
초기값 세팅
const n = maze.length;
const m = maze[0].length;
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];
let bs;
let rs;
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
switch(maze[i][j]) {
case 2:
bs = [i, j];
break;
case 1:
rs = [i, j];
break;
}
}
}
const visited = Array.from({ length: 2 }, () =>
Array.from({ length: n }, () =>
Array.from({ length: m}, () => 0)
)
);
visited[0][bs[0]][bs[1]] = 1;
visited[1][rs[0]][rs[1]] = 1;이 부분은 초기값들을 세팅하는 부분입니다.
visited를 3차원 배열로 선언 및 할당하고 0번째는 파란색, 1번째는 빨간색 공용 visited로 사용합니다.
그래프 탐색 조건 분류
그래프 탐색할 때의 분류는 총 4가지로 합니다.
1. 빨간색, 파란색 모두 목표 지점에 도달했을 때
이 경우 탐색 종료 지점이므로 answer Array에 결과를 push하고 return 합니다.
2. 빨간색, 파란색 둘 다 목표 지점에 도달하지 못했을 때
이 경우 파란색, 빨간색 공을 둘다 이동시켜서 다음 단계로 진행해야합니다. 파란색, 빨간색 중 임의의 공을 먼저 이동시킵니다.
이동 시킬 시 조건 탐색은
1. 바운드를 넘어가지 않는지
2. visited값이 0인지
3. maze값이 5가 아닌지(벽이 아닌지)
순서로 확인합니다.
해당 조건을 모두 만족시키면 다음 공의 조건을 확인합니다. 이 때는 위의 조건 탐색에서 두 공이 같은 위치로 이동했는지를 추가로 확인해야합니다.
마지막으로 위의 조건을 모두 충족시켰을 때 공이 서로 자리를 바꾼 경우를 제외 시켜 줍니다.
if (!((nbx === rx && nby === ry) && (bx === nrx && by === nry)))
이 모든 경우를 만족하면 다음 단계로의 탐색이 준비가 끝난것입니다!! 이제 visited를 1로 바꿔주고 dfs를 재귀 호출해줍니다. dfs재귀 호출이 끝난 시점에서는 다음 탐색을 위해 다시 visited를 0으로 바꿔주어야 합니다.!!
**3. 둘 중에 하나만 목표 지점에 도달했을 때
둘 중에 하나만 목표 지점에 도달했을 때는 도달한 공은 가만히 놔두고 도달하지 않은 공에 대해서만 탐색을 이어나가면 됩니다!!
사실 maze의 조건이 가로 길이 <= 4, 세로 길이 <= 4이기 때문에 BFS로 구현해도 시간 초과나 메모리 초과가 나지는 않을 것 같습니다만 재귀 호출 방법이 출제자의 의도인 것 같아 풀이를 이렇게 하였습니다.
하나의 공이였을 경우 많이 보던 유형의 문제이였겠지만 공이 2개이기 때문에 탐색 조건들을 생각하는 것이 까다로웠던 문제였습니다!
