정리
-
얼음 겉면 녹이기 BFS (+무한루프)
https://softeer.ai/app/assessment/index.html?xid=425977&xsrfToken=4jy3IoL7ESSbYv0ydF7qXRUT2uocG1RR&testType=practice -
주어진 좌표 + 경유지 DFS
https://softeer.ai/app/assessment/index.html?xid=424432&xsrfToken=qx9lXga5zRotbV1i39TNZIrUAqMxVY0F&testType=practice -
덩어리 찾고 Count BFS
https://softeer.ai/app/assessment/index.html?xid=411255&xsrfToken=kkSZln0W4nS9VUKiTBpLU7MRJOsR6yxD&testType=practice
기억해야 할 점
백트래킹은 주로 DFS에서 씀 (DFS실행후 완료되지 않았을 때)
두 명의 DFS를 진행시 사용함
(Lv.3) 함께하는 효도
초기 나의 코드
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
// bfs를 활용하여 움직이는 대신, 최댓값으로만 이동해야함
// 3초 동안 (처음 포함)
// 친구랑 겹치면 안됨 -> 어차피 좌표가 두 개 주어지니까 한 번 하고 그 다음 한 번 하는데
// 이미 들린 곳은 0으로 표시해서 계속 바꿔가면 되는데
// 가장 큰 값으로만 이동을 해야함
function solution() {
const [n, m] = input[0].split(' ').map(Number);
let maps = [];
for(let i=1; i<=n; i++) maps.push(input[i].split(' ').map(Number));
let friends = [];
for(let i=5; i < input.length; i++) friends.push(input[i].split(' ').map(Number))
const firstFriendX = friends[0][0]-1;
const firstFriendY = friends[0][1]-1;
let visited = [];
for(let i=0; i<n; i++) visited.push(new Array(n).fill(false))
visited[firstFriendX][firstFriendY] = true;
// console.log(visited)
let queue = [];
queue.push([firstFriendX, firstFriendY])
// console.log(queue)
const dx = [1, 0, -1, 0];
const dy = [0, 1, 0, -1];
let ans = 0;
for(let i=0; i < friends.length; i++) {
// 친구들이 도는 횟수 반복
for (let j=0; j < 4; j++) {
while(queue.length) {
let [x, y] = queue.shift();
let max = 0;
let targetPos = [];
// 최대값 찾기
// ★ 이렇게 최대값을 찾을 땐 정석루트처럼 가는 게 아니라
// 최대값으로 이동하기 위한 모든 처리와 조건을 다 걸어주고 진행
for(let d=0; d < 4; d++) {
let nx = x + dx[d];
let ny = y + dy[d];
if (nx >= 0 && nx < n && ny >= 0 < ny < n && !visited[nx][ny]) {
if (maps[nx][ny] > max) {
max = maps[nx][ny]
targetPos = [[nx, ny]];
} else if (maps[nx][ny] === max) {
targetPos = [[nx, ny]];
}
}
}
console.log(max)
// dx 좌표를 도는 횟수 반복
let nx = x + dx[k];
let ny = y + dy[k];
if (nx > 0 && nx < n && ny > 0 && ny < n && !visited[nx][ny] && maps[nx][ny] === max && maps[nx][ny] !== 0) {
maps[nx][ny] = 0;
visited[nx][ny] = true;
queue.push([nx, ny]);
// ans += maxX
// ans += maxY
max = 0;
}
}
}
ans += max
}
console.log('ans', ans)
}
solution()힌 두시간을 풀었지만 좋은 접근이더라도 해결은 하지 못했음
풀이
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
function solution() {
// 입력 파싱
const [n, m] = input[0].split(' ').map(Number);
let maps = [];
for (let i = 1; i <= n; i++) {
maps.push(input[i].split(' ').map(Number));
}
let friends = [];
for (let i = n + 1; i < input.length; i++) {
friends.push(input[i].split(' ').map(Number).map(v => v - 1)); // 좌표 1 감소
}
// 방향 벡터 (상, 우, 하, 좌)
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];
// 친구가 이동할 수 있는 모든 경로를 찾는 DFS 함수
function findAllPaths(path, x, y, paths) {
if (path.length === 4) { // 최대 3칸 이동 가능
paths.push([...path]);
return;
}
for (let i = 0; i < 4; i++) {
let nx = x + dx[i];
let ny = y + dy[i];
// 범위 내에 있고, 아직 방문하지 않은 경우
if (nx >= 0 && nx < n && ny >= 0 && ny < n && !path.some(p => p[0] === nx && p[1] === ny)) {
path.push([nx, ny]);
findAllPaths(path, nx, ny, paths);
path.pop();
}
}
}
// 가능한 경로 조합을 생성하는 함수 (Cartesian Product)
function generateCombinations(arrays) {
return arrays.reduce((acc, curr) => {
return acc.flatMap(d => curr.map(e => [...d, e]));
}, [[]]);
}
// 선택한 경로에 대한 열매 수확량을 계산하는 함수
function calculateHarvest(comb) {
let totalHarvest = 0;
let visited = new Set();
for (let path of comb) {
for (let [x, y] of path) {
if (visited.has(`${x},${y}`)) return 0; // 중복 방문하면 무효
visited.add(`${x},${y}`);
totalHarvest += maps[x][y];
}
}
return totalHarvest;
}
// 각 친구가 이동할 수 있는 모든 경로 찾기
let allPaths = [];
for (let friend of friends) {
let paths = [];
findAllPaths([friend], friend[0], friend[1], paths);
allPaths.push(paths);
}
// 가능한 모든 이동 조합 생성
let allCombinations = generateCombinations(allPaths);
// 최대 수확량 찾기
let maxHarvest = 0;
for (let combination of allCombinations) {
maxHarvest = Math.max(maxHarvest, calculateHarvest(combination));
}
console.log(maxHarvest);
}
solution();
(Lv.3) 택배 마스터 광우
여기에서 배운점 (문법정리)
가장 중요한 핵심 ★★★
- if문을 만나서 종료되는 건 dfs(count + 1, result)로 호출 한 애, 그 다음 백트래킹을 진행하는 애는 남아 있기 때문에 다시 백트래킹이 가능
- 그럴게 백트래킹을 진행하다가 더 이상 새로운 숫자 조합이 없을 때 진짜 종료
백트래킹 과정
조건에 맞을 때까지 돌며 배열의 인덱스를 조합할 때 인덱스 값을 순환시키는 방법
// 일하는 횟수 (4번 만큼 반복)
for (let i = 0; i < k; i++) {
let weight = 0;
// 20이하일 때만 담아줌
while (weight + result[idx] <= m) {
// 무게가 20 될 때까지 while을 통해 반복
weight += result[idx];
// ★ 인덱스를 n으로 나누며 idx순환
idx = (idx + 1) % n;
}
totalWeight += weight;
}
idx = (idx + 1) % n; 처럼 인덱스를 나누어주어 해당 인덱스의 값을 올려줌DFS 종료
- DFS 종료시 내가 알던대로 맨 위에다가 종료 조건을 달아주면 됨
- 그렇기 때문에 마지막 DFS 실행시에는 인덱스가 오바되는 값이 있더라도 그 값에 의해 종료
풀이
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
function solution() {
const [n, m, k] = input[0].split(' ').map(Number);
const rails = input[1].split(' ').map(Number);
let visited = new Array(n).fill(false);
let minWeight = Infinity;
// dfs를 활용
// ★ 여기에서 result => 길이 N의 빈 배열
function dfs(count, result) {
// 레일의 갯수가 다채워졌을 때
if (count === n) {
// 모든 레일의 조합에서 5가 됐을 때를 totalWeight에 중간 저장
// => ★★ 길이가 5가 됐을 때에 minWeight값을 갖고 있으면서 모든 조합의 경우와 비교
// 진짜로 종료시에는 더이상 새로운 5의 조합이 없을 때 종료
// "여기에서 종료되는 거은 dfs(count+1, result)로 한번 더 호출된 애"
// => 그 후 다시 마저 진행 중이던 아래의 dfs(4, [...])로 돌아감
let totalWeight = getWeight(result);
minWeight = Math.min(minWeight, totalWeight);
return;
}
// dfs를 통해 길이가 5가 될 때까지 모든 조합을 다 찾음
for (let i = 0; i < n; i++) {
if (!visited[i]) {
visited[i] = true;
// ★ result의 count번째 (인덱스번쨰) 에다가 rails[i]를 할당
// 어차피 count가 5로 전달되면 상위 if문에서 막힘
result[count] = rails[i];
dfs(count + 1, result);
// ★★★ 여기 백트래킹을 통해서 모든 길이 5의 조합을 탐색
visited[i] = false;
}
}
}
// 무게를 구하는 함수
function getWeight(result) {
let totalWeight = 0;
let idx = 0;
// 일하는 횟수 (4번 만큼 반복)
for (let i = 0; i < k; i++) {
let weight = 0;
// 20이하일 때만 담아줌
while (weight + result[idx] <= m) {
// 무게가 20 될 때까지 while을 통해 반복
weight += result[idx];
// ★ 인덱스를 n으로 나누며 idx순환
idx = (idx + 1) % n;
}
totalWeight += weight;
}
return totalWeight;
}
dfs(0, new Array(n));
console.log(new Array(n))
console.log(minWeight);
}
solution();
(Lv.3) 나무 섭지 ★★
여기에서 배운 점
시간초과가 날 땐 shift()를 사용하지 않아보기
풀이
- 유령보다 남우가 더 먼저 도착 할 때만 정상적으로 탈출 가능
- 우선 주어진 값에 따라 남우, 유령, 탈출구의 위치를 각각 배열에 저장
- 유령은 여러 마리가 나오므로 여러 번 삽입
- 유령 별로 BFS를 실시하는데 유령의 위치에 존재 위치에 0을 삽입하여 탈출구까지 거리를 계산할 수 있도록 함
- 여기에서 유령이 여러마리일 때 shift를 사용시 시간초과 그렇기 때문에 ghostIndex란 값을 두어서 그 값을 즐가시키며 ghost들을 모두 bfs 돌려줌 -> 유령이 이동시 각각의 거리가 저장되어있음
- 여기에서 어차피 가장 가까운 애가 남우를 잡으면 되므로 "가까운 애의 값으로 탈출구까지의 거리를 계산"
- 그 후 남우 DFS를 수행하면서 dist를 추가
- dist값이 유령보다 작을 떄만 이동을 하고 크면 어차피 잡히는 거니까 이동하지않음
- 결론적으로, 남우가 출구에 도착했을 때 Infinity(도달하지 못함)이라면 No 도달했으면 Yes
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
function solution() {
const [n, m] = input[0].split(' ').map(Number);
const maps = [];
for(let i=1; i<input.length; i++) maps.push(input[i].split(''));
let ghostVisited = [];
for(let i=0; i<n; i++) ghostVisited.push(new Array(m).fill(false));
const namPos = [];
let ghostQueue = [];
const doorPos = [];
for(let i=0; i<n; i++) {
for(let j=0; j<m; j++) {
if(maps[i][j] === 'N') {
namPos.push([i, j]);
} else if (maps[i][j] === 'G') {
ghostQueue.push([i, j]);
} else if (maps[i][j] === 'D') {
doorPos.push([i, j]);
}
}
}
const [exitX, exitY] = doorPos[0];
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];
// ✅ 유령 BFS (shift() 없이 index 사용)
let ghostDis = [];
for(let i=0; i<n; i++) ghostDis.push(new Array(m).fill(Infinity));
for (let i=0; i<ghostQueue.length; i++) { // 유령 초기 위치 거리 0 설정
let [gx, gy] = ghostQueue[i];
ghostDis[gx][gy] = 0;
}
let ghostIndex = 0; // shift() 대체용 index 사용
while (ghostIndex < ghostQueue.length) {
const [x, y] = ghostQueue[ghostIndex++]; // shift() 대신 index 증가
for (let i = 0; i < 4; i++) {
let nx = x + dx[i];
let ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && ghostDis[nx][ny] === Infinity) {
ghostDis[nx][ny] = ghostDis[x][y] + 1;
ghostQueue.push([nx, ny]);
}
}
}
// ✅ 남우 BFS
let namQueue = [[namPos[0][0], namPos[0][1], 0]]; // (x, y, 이동 거리)
let namVisited = [];
for(let i=0; i<n; i++) namVisited.push(new Array(m).fill(false));
let namToDoor = Infinity;
let namIndex = 0; // shift() 대체용 index 사용
while (namQueue.length) {
let [x, y, dist] = namQueue.shift(); // shift() 대신 index 증가
// 출구 도착시 종료
if(x === exitX && y === exitY) {
namToDoor = dist;
break;
}
for(let i=0; i<4; i++) {
let nx = x + dx[i];
let ny = y + dy[i];
// 다음 방문 거리가 유령보다 늦게 도착하면 탐색하지 않음
if (nx >= 0 && nx < n && ny >= 0 && ny < m && maps[nx][ny] !== '#'
&& dist + 1 < ghostDis[nx][ny] && !namVisited[nx][ny]) {
namVisited[nx][ny] = true;
namQueue.push([nx, ny, dist + 1]);
}
}
}
console.log(namToDoor !== Infinity ? 'Yes' : 'No');
}
solution();
GINI야 도와줘 ★★
여기에서 배운점
- 상하좌우로 확산하는 소나기들을 어렵게 생각하지 말고 rainTime 배열을 만들어서 각 소나기가 지나갈 때에 해당하는 시간을 넣어주면 됨
풀이
생각했던 것만큼 어렵지는 않았지만 rainTime이란 접근법을 떠올리기까지는 아쉬운 점이 많았던 거 같다
dist를 통해 거리 계싼하는 방법은 두고두고 복습하며 따져야할 것 같다
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
function solution() {
const [n, m] = input[0].split(' ').map(Number);
const maps = [];
for (let i = 1; i <= n; i++) maps.push(input[i].split(''));
let rainTime = [];
let visited = [];
for (let i = 0; i < n; i++) {
rainTime.push(new Array(m).fill(0));
visited.push(new Array(m).fill(false));
}
let rainQueue = []; // 🌧️ 소나기 확산을 위한 BFS 큐
let queue = []; // 🚗 태범이 이동을 위한 BFS 큐
let homeX, homeY; // 🏠 집의 위치 저장
let startX, startY; // 🚗 태범이의 시작 위치 (세차장)
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (maps[i][j] === 'W') {
startX = i;
startY = j;
} else if (maps[i][j] === 'H') {
homeX = i;
homeY = j;
} else if (maps[i][j] === '*') {
rainQueue.push([i, j]); // 소나기 시작 위치 저장
rainTime[i][j] = 1; // 소나기 시작 시간은 1로 설정
}
}
}
/**
* 🌧️ 소나기 확산 BFS
* - 초기 소나기 위치에서 BFS 탐색을 진행하며, 비가 내리는 시간을 기록
* - 소나기는 강('X')과 집('H')에는 퍼지지 않음
*/
function spreadRain() {
let queue = [...rainQueue]; // 초기 소나기 위치를 큐에 삽입
while (queue.length) {
let [x, y] = queue.shift(); // 큐에서 현재 위치(x, y) 꺼내기
for (let i = 0; i < 4; i++) { // 4방향 탐색 (상, 우, 하, 좌)
let nx = x + dx[i];
let ny = y + dy[i];
// 🔹 이동 범위 벗어나거나, 강('X') 또는 이미 비가 내린 곳은 패스
if (nx >= 0 && nx < n && ny >= 0 && ny < m && maps[nx][ny] === '.' && rainTime[nx][ny] === 0) {
rainTime[nx][ny] = rainTime[x][y] + 1; // 현재 시간 + 1
queue.push([nx, ny]); // 다음 위치를 큐 삽입
}
}
}
}
/**
* 🚗 태범이 이동 BFS
* - 매 턴마다 이동 가능 여부를 체크하며 최단 경로 탐색
* - 소나기가 내리기 전에 도착할 수 있는지 확인
*/
function moveCar() {
let queue = [[startX, startY, 1]];
visited[startX][startY] = true;
while (queue.length) {
let [x, y, time] = queue.shift();
// 🏠 집에 도착하면 최단 거리 출력
if (x === homeX && y === homeY) {
console.log(time - 1); // 이동 시간 출력 (초기값 1 제외)
return;
}
for (let i = 0; i < 4; i++) {
let nx = x + dx[i];
let ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && maps[nx][ny] !== 'X' && maps[nx][ny] !== '*') {
// 🚨 비가 아직 오지 않았거나 현재 시간 + 1이 비가 내리는 시간보다 작다면 이동 가능
if (rainTime[nx][ny] === 0 || time + 1 < rainTime[nx][ny]) {
visited[nx][ny] = true; // 방문 처리
queue.push([nx, ny, time + 1]); // 다음 위치 큐에 삽입
}
}
}
}
console.log("FAIL");
}
spreadRain(); // 🌧️ 먼저 소나기 확산 실행
moveCar(); // 🚗 태범이 이동 실행
}
solution();
나무 섭지 & GINI 재풀이
나무섭지 풀이
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
function solution() {
const [n, m] = input[0].split(' ').map(Number);
let maps = [];
for(let i=1; i<input.length; i++) maps.push(input[i].split(''))
let ghostTime = [];
let visited = [];
for(let i=0; i<n; i++) {
// 맨처음부터 0이라면 Infinity로 해서 해주는 게 좋음
ghostTime.push(new Array(m).fill(Infinity));
visited.push(new Array(m).fill(false));
}
let namX, namY;
let exitX, exitY;
let ghostPos = [];
for(let i=0; i<n; i++) {
for(let j=0; j<m; j++) {
if (maps[i][j] === 'N') {
namX = i;
namY = j;
} else if (maps[i][j] === 'D') {
exitX = i;
exitY = j;
} else if (maps[i][j] === 'G') {
ghostPos.push([i, j]);
ghostTime[i][j] = 0;
}
}
}
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];
function ghostBFS() {
let ghostQueue = [...ghostPos];
let ghostIndex = 0;
while(ghostIndex < ghostQueue.length) {
let [x, y] = ghostQueue[ghostIndex++];
for(let i=0; i<4; i++) {
let nx = x + dx[i];
let ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && ghostTime[nx][ny] === Infinity) {
ghostTime[nx][ny] = ghostTime[x][y] + 1;
ghostQueue.push([nx, ny])
}
}
}
}
function namwuBFS() {
let namQueue = [[namX, namY, 1]];
visited[namX][namY] = true;
let namIndex = 0;
while(namIndex < namQueue.length) {
let [x, y, dist] = namQueue[namIndex++];
if(x === exitX && y === exitY) {
console.log("Yes")
return;
}
for(let i=0; i<4; i++) {
let nx = x + dx[i];
let ny = y + dy[i];
if(nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && maps[nx][ny] !== '#') {
if(dist < ghostTime[nx][ny]) {
visited[nx][ny] = true;
namQueue.push([nx, ny, dist+1])
}
}
}
}
console.log('No')
}
ghostBFS()
namwuBFS()
}
solution()GINI 풀이
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
function solution() {
const [n,m] = input[0].split(" ").map(Number)
const maps = [];
for(let i=1; i<input.length; i++) maps.push(input[i].split(""))
let startX, startY
let homeX, homeY
let rainPos = [];
let rainTime = [];
let visited = [];
for(let i=0; i<n; i++) {
rainTime.push(new Array(m).fill(0));
visited.push(new Array(m).fill(false));
}
for(let i=0; i<n; i++) {
for(let j=0; j<m; j++) {
if(maps[i][j] === 'H') {
homeX = i;
homeY = j;
} else if (maps[i][j] === 'W') {
startX = i;
startY = j;
} else if (maps[i][j] === '*') {
rainPos.push([i, j])
rainTime[i][j] = 1;
}
}
}
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];
function rainBFS() {
let rainQueue = [...rainPos]
while(rainQueue.length) {
let [x, y] = rainQueue.shift()
for (let i=0; i<4; i++) {
let nx = x + dx[i];
let ny = y + dy[i];
if(nx >= 0 && nx < n && ny >= 0 && ny < m && maps[nx][ny] === '.' && rainTime[nx][ny] === 0) {
rainTime[nx][ny] = rainTime[x][y] + 1; // 다음 애는 갈 애에 +1
rainQueue.push([nx, ny])
}
}
}
}
function taebumBFS() {
let taebumQueue = [[startX, startY, 1]];
visited[startX][startY] = true;
while(taebumQueue.length) {
let [x, y, time] = taebumQueue.shift();
if(x === homeX && y === homeY) {
// 직전에 바로 +1 해줬으니 1뻄
console.log(time - 1);
return;
}
for(let i=0; i<4; i++) {
let nx = x + dx[i];
let ny = y + dy[i];
//-> maps[nx][ny] === '.' 이렇게 되면 집을 못 찾음 그래서 or로 넣어주어야함
if(nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && (maps[nx][ny] === '.' || maps[nx][ny] === 'H') ) {
// if(nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && maps[nx][ny] !== 'X' && maps[nx][ny] !== '*') {
if (rainTime[nx][ny] === 0 || time + 1 < rainTime[nx][ny]) {
visited[nx][ny] = true;
taebumQueue.push([nx, ny, time+1])
}
}
}
}
console.log("FAIL")
}
rainBFS()
taebumBFS()
}
solution()
기록, 꺼내 쓸 수 있는 즐거움