알고리즘
[JS] 백준 1978 : 알파벳 - 그래프, 이론그래프, 탐색, 깊이 우선 탐색,백트래킹
이즈흐
2023. 8. 1. 00:45
https://www.acmicpc.net/problem/1987
1987번: 알파벳
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으
www.acmicpc.net
풀이방법
1.DFS로 상하좌우를 탐색한다.
2. 탐색하면서 지나온 알파벳은 배열에 저장한다.
3. 다음 알파벳을 검사할 때 저장해놓았던 배열을 indexOf로 검사한다
4. -1이 나오면 겹치는 알파벳이 없는 것이므로 진행해준다.
5. 이때 visited라는 2차원 배열로 방문표시를 해줘야 무한재귀가 걸리지않는다.
6. 또한 DFS로 뻗어나갈 때 상하 좌우 모든 경우로 뻗어나가야하므로 저장했던 알파벳을 다시빼주고, 방문표시도 제외해서 다음 반복을 준비한다( 즉 오른쪽으로 검사했다면 다음은 왼쪽 아래쪽 위쪽도 뻗어가면서 최대 경로를 찾아야한다.)
내 제출
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");
let [R,C]=input.shift().split(" ").map(Number);
let arr = [];
for (var i = 0; i < R; i++){
arr.push(input.shift().split(""));
}
let remember = [];
let dx = [1, 0, 0, -1];
let dy = [0, 1, -1, 0];
let visited = Array.from({length: R},()=>Array(C).fill(0))
let max = 0;
function DFS(L, y, x) {
for (var i = 0; i < 4; i++){
let nx = x + dx[i];
let ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < C && ny < R && visited[ny][nx] == 0) {
if (remember.indexOf(arr[ny][nx]) == -1) {
remember.push(arr[ny][nx]);
visited[ny][nx] = 1;
DFS(L + 1, ny, nx);
remember.pop();
visited[ny][nx] = 0;
}
}
}
max=Math.max(max,L)
}
visited[0][0] = 1;
remember.push(arr[0][0]);
DFS(1, 0, 0);
console.log(max)
💢어려웠던 점
1. DFS를 진행할 때 처음에 오른쪽으로 진행한뒤 다시 되돌아오는 것을 안해줘서 최대 경로가 나오지 않았다.
- 상하좌우 4개의 경우 중 오른쪽으로 뻗어나가고 만약 그길이 아니면 다시 되돌아와서 다른 길로 가야하는데 그것을 위해 저장했던 알파벳을 빼주고 방문표시도 다시 제외해줘야한다.
...
if (remember.indexOf(arr[ny][nx]) == -1) {
remember.push(arr[ny][nx]);
visited[ny][nx] = 1;
DFS(L + 1, ny, nx);
remember.pop();
visited[ny][nx] = 0;
}
...
728x90
반응형
LIST