소프티어

제출 코드 :

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let lineNo = 0;
const dir = [[-1,0], [0,1], [1,0], [0, -1]];
let n, m;
const arr = [];
const fArr = [];


const isOk = (i, j) => {
    return i >=1 && i<=n && j>=1 && j<=n;
}


const solve = () => {
    const searchRoute = (curFIndex) => {
        const result = [];
        const findARoute = () => {
            const visited = Array.from({length: n+1}, () => new Array(n+1).fill(false));
            const s = [];
            const curFI = fArr[curFIndex][0];
            const curFJ = fArr[curFIndex][1]
            s.push({i:curFI, j: curFJ, time: 0, num: arr[curFI][curFJ]})
            visited[curFI][curFJ] = true;
            
            const dfs = (curI, curJ, curTime) => {
                if (curTime ===3) {
                    result.push([{i:curFI, j: curFJ, time: 0, num: arr[curFI][curFJ]}, ...s.slice(0,)]);
                    return;
                }
                for (let i=0; i<4; i+=1) {
                    const [newI, newJ] = [curI + dir[i][0], curJ + dir[i][1]];
                    if (isOk(newI, newJ) && !visited[newI][newJ]) {
                        visited[newI][newJ] = true;
                        s.push({i:newI, j:newJ, time: curTime+1, num: arr[newI][newJ]});
                        dfs(newI, newJ, curTime + 1);
                        visited[newI][newJ] = false;
                        s.pop();
                    }
                }
            };
            while(s.length>0) {
                const {i, j, time} = s.pop();
                dfs(i, j, time);
            }
        }
        findARoute();
        return result;
    }
    // 1. 가능한 루트 dfs로 다 탐색
    const allRoute = [];
    for (let i=0; i<fArr.length; i+=1) {
        allRoute.push(searchRoute(i));
    }
    
    // 2. 그 경로들로 dfs로 전부 탐색
    let foundedR = [];
    const visitedTime = Array.from({length: 4}, () => Array.from({length:n+1}, () => new Array(n+1).fill(false)));
    const visitedFruit = Array.from({length:n+1}, () => new Array(n+1).fill(0));
    const s = [];  
    const dfs = (fIndex) => {
        if (fIndex === m) {
            foundedR.push(s.slice(0,));
            return;
        }


        const routes = allRoute[fIndex];
        // 여기서 for돌면서 하나 고르고.
        for (const r of routes) {
            // 그 루트 돌면서 체크.
            // 그 시간에 없는지
            // if (r.every((x) => !visitedTime[x.time][x.i][x.j] && !visitedFruit[x.i][x.j])) {
            if (r.every((x) => !visitedTime[x.time][x.i][x.j])) {
                // + 남이 따간 곳 방문하면 num 0으로 바꾸는 로직 추가
                const processedR = r.map((x) => {
                    if (visitedFruit[x.i][x.j]>0) return {...x, num: 0};
                    else return x;
                })
                // 없으면 방문 체크 후 push
                r.forEach((x) => {
                    visitedTime[x.time][x.i][x.j] = true;
                    visitedFruit[x.i][x.j] += 1;
                });
                // s.push(r);
                s.push(processedR);
                // dfs
                dfs(fIndex+1);
                // 방문 해제 후 pop 
                r.forEach((x) => {
                    visitedTime[x.time][x.i][x.j] = false;
                    visitedFruit[x.i][x.j] -= 1;
                });
                s.pop();
            }
        }
        
    }
    dfs(0);


    let max = 0;
    for (const fR of foundedR) {
        max = Math.max(max, fR.reduce((a, b) => a + b.reduce((aa, bb) => aa + bb.num, 0), 0));
    }


    console.log(max);
};


rl.on('line', (line) => {
    if (lineNo === 0) {
        [n,m] = line.split(" ").map((x) => 1 * x);
        arr.push(new Array(n+1).fill(-1));
    }
    else if (lineNo <=n) arr.push([-1, ...line.split(" ").map((x) => 1 * x)]);
    else fArr.push(line.split(" ").map((x) => 1 * x));
    lineNo+=1;
}).on('close', () => {
    solve();
    process.exit(0);
});

풀이:

알고리즘 문제풀이가 너무 오랜만이라 아직 코드가 많이 조잡합니다. 죄송합니다..

1. 각 친구들이 이동 가능한 모든 경로를 dfs로 구합니다.
2. 그 경로 중에서, 같은 시간에, 같은 장소에만 없으면 허용이라는 조건을 만족하는 경로들을 dfs로 전부 찾습니다.
3. 그렇게 찾은 경로에서 max 값을 찾아 출력합니다.

처음에 저는 루트를 결정할 때 그 시간에, 그 좌표에 겹치지 않기 + 다른 친구가 방문한 좌표면 가지 않기 라고 생각해서

if (r.every((x) => !visitedTime[x.time][x.i][x.j] && !visitedFruit[x.i][x.j]))

이렇게 풀었더니, 마지막 테스트케이스만 틀렸습니다.

뭐가 문제일까, 생각을 해보니 문제에서 "한 나무에 여러 친구가 방문하게 되더라도 열매는 딱 한 번만 수확이 가능합니다"라고 하는 것을 발견했습니다.

즉 visited 처리 이슈였습니다.

그래서 true/false로 관리하던 방문한 좌표를 숫자로 바꿔서 (친구들 중 1명 이상 방문할 수 있으니)

const visitedFruit = Array.from({ length: n + 1 }, () =>
    new Array(n + 1).fill(0)
  );

방문할 때마다 카운트를 올리고, dfs에서 return 할 때 하나씩 내리고

해당 좌표의 카운트가 0일 때에만 열매 개수를 그대로 올리고, 0이 아니면 남은 열매 개수를 0으로 하여 경로를 저장해두고

그 경로 중 max값을 출력하니 마지막 테스트케이스도 통과했습니다!

혹시 저와 같은 이유로 막혀있으신 분들 계실 수도 있을 것 같아 공유합니다.