[백준/21736/JavaScript] 헌내기는 친구가 필요해 풀이 (dfs, bfs, 자바스크립트, js)
[백준/21736/javascript] 헌내기는 친구가 필요해 풀이
( dfs, bfs, 자바스크립트, js)
1. 문제
https://www.acmicpc.net/problem/21736
2. 문제 풀이
1. BFS
1. 큐에 시작 지점 위치를 저장한다. (I)
2. 큐가 빌 때까지 BFS를 반복한다. BFS는 ' 이동하게 될 위치를 기준으로' 확인한다.
2.1. 상,하,좌,우 탐색
- 주어진 범위 (n,m)를 벗어나면 continue
- 'X'이면 벽이므로 continue
- 'P'이면 사람이므로 1 추가
- 'O'거나 'P'이면 새로운 위치에 있는 값을 찾은 사람 수로 업데이트하고, 큐에 새로운 위치 좌표 추가 (방문처리)
2. DFS
1. 시작 지점(I)에서 DFS를 수행한다. DFS는 '이동한 위치를 기준으로' 확인한다
2. 상,하,좌,우 dfs를 재귀적으로 호출하여 탐색
- 주어진 범위 (n, m)를 벗어나면 continue
- 'X'이면 벽이므로 continue
- 'P'이면 사람이므로 1 추가
- 'O'거나 'P'이면 위치에 있는 값을 찾은 사람 수로 업데이트 (방문처리)
3. 코드
3-1. BFS 코드
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let N = null;
let M = null;
let I = null; // 도연이 시작 위치 [row, col]
let nCount = 0;
let data = [];
const solution = (N, M, I, data) => {
let queue = [I]; // 시작 지점 저장
// 도연의 위치는 탐색 안하는 곳으로 설정
let peopleCount = 0; // 사람 수
let headIdx = 0; // 배열을 큐로 쓰되, headIdx를 관리해서 O(1)로 꺼내도록 한다.
data[I[0]][I[1]] = "X";
// 상, 하, 좌, 우
const dRow = [-1, 1, 0, 0];
const dCol = [0, 0, -1, 1];
while (headIdx < queue.length) {
// shift() 대신 headIdx를 써서 O(1)로 꺼낸다.
let [row, col] = queue[headIdx++]; // 현 위치 저장
// let [row, col] = queue.shift(); // 현 위치 저장
// 상, 하, 좌, 우 앞으로 가게 될 미래 위치 구하기
for (let i = 0; i < 4; i++) {
let newRow = row + dRow[i];
let newCol = col + dCol[i];
// 새로운 위치가 범위를 벗어나거나 벽이라면 패스
if (
newRow < 0 ||
newRow >= N ||
newCol < 0 ||
newCol >= M ||
data[newRow][newCol] === "X"
) {
continue;
}
// 새로운 위치에 사람이 있다면 (P) count 1 증가
if (data[newRow][newCol] === "P") {
peopleCount++;
}
// 새로운 위치가 빈 공간(O) 이거나 사람이 있다면 현재 위치 저장!
queue.push([newRow, newCol]); // 현재 위치 추가
data[newRow][newCol] = "X"; // 그냥 벽으로 업데이트
}
// console.log(row, col);
// data.forEach((item) => {
// console.log(item);
// });
}
if (peopleCount > 0) {
console.log(peopleCount);
} else {
console.log("TT");
}
};
rl.on("line", (line) => {
if (!N) {
[N, M] = line.split(" ").map((item) => +item); // 캠퍼스 크기 입력 (nxm)
} else {
data.push(
line.split("").map((item, index) => {
if (item === "I") {
I = [nCount, index]; // 도연이 위치 저장
}
return item;
})
);
nCount++; // 카운트 증가
}
if (nCount === N) {
// n개 데이터 입력했다면
solution(N, M, I, data);
rl.close();
}
}).on("close", () => {
process.exit();
});
※ 참고 : 시간 초과 해결 방법
- 처음에 큐의 첫번째 요소를 빼는 코드를 queue.shift()로 했다가 시간 초과가 났다.
왜냐하면 shift()는 첫 번째 요소를 빼고 나머지 요소를 모두 앞으로 당겨주는 것이기 때문이다..
- 그래서 현재의 코드와 같이 큐의 첫 요소를 shift 하지 않고, index로 큐에 값을 확인하는 방식으로 변경하여 시간초과를 해결했다.
while (headIdx < queue.length) {
// shift() 대신 headIdx를 써서 O(1)로 꺼낸다.
let [row, col] = queue[headIdx++]; // 현 위치 저장
// let [row, col] = queue.shift(); // 현 위치 저장1. queue : 내부에 [row, col] 쌍을 순서대로 저장
2. headIndx : 다음에 꺼낼(처리할) 인덱스를 가리키는 포인터 역할
3. queue[headIdx] :현재 처리할 위치가 된다.
4. 반복 조건 while (headIdx < queue.length) : 아직 처리하지 않은 좌표가 남아있는가?를 묻는 것
- 예를 들어, 현재 headIdx = 0이고 queue.length = 1이면 0 <1이므로 큐에 탐색해야 할 좌표가 남아있다는 뜻이므로 반복을 진행한다.
3-2. DFS 코드
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let N = null;
let M = null;
let I = null; // 도연이 시작 위치 [row, col]
let nCount = 0;
let data = [];
let personCount = 0;
const dfs = (row, col) => {
// console.log(row, col);
// data.forEach((item) => {
// console.log(item);
// });
// 주어진 범위를 벗어나면 즉시 종료하자.
if (row < 0 || row >= N || col < 0 || col >= M) {
// *벽이라도 패스
return;
}
if (data[row][col] === "X") {
return;
}
// * 사람이 있는 곳이라면 "P" count +=1
if (data[row][col] === "P") {
personCount++; // 사람수 1 증가
}
// * 왔던 위치 방문처리
data[row][col] = "X";
// console.log(personCount);
// * 내 위치 기준으로 상,하,좌,우를 dfs로 찾는다.
const dRow = [-1, 1, 0, 0];
const dCol = [0, 0, -1, 1];
for (let i = 0; i < 4; i++) {
dfs(row + dRow[i], col + dCol[i]);
}
return;
};
const solution = (N, M, I, data) => {
// 도연의 위치는 탐색 안하는 곳으로 설정
// * dfs 수행
// 시작 위치부터 한다.
dfs(I[0], I[1]);
if (personCount > 0) {
console.log(personCount);
} else {
console.log("TT");
}
};
rl.on("line", (line) => {
if (!N) {
[N, M] = line.split(" ").map((item) => +item); // 캠퍼스 크기 입력 (nxm)
} else {
data.push(
line.split("").map((item, index) => {
if (item === "I") {
I = [nCount, index]; // 도연이 위치 저장
}
return item;
})
);
nCount++; // 카운트 증가
}
if (nCount === N) {
// n개 데이터 입력했다면
solution(N, M, I, data);
rl.close();
}
}).on("close", () => {
process.exit();
});
4. 마무리
읽어주셔서 감사합니다~
도움이 되셨다면 공감 부탁드립니다 😊
피드백은 언제나 환영입니다 👍