소프티어

T가 100이 최대라서 재귀 DFS 되겠지 하고 썼는데, 런타임 에러 나니깐 쓰면 안됩니다. 아마도.

const fs = require('fs');
const input = fs.readFileSync('input.txt', 'utf8').trim().split(/\n+/);
const [N, T] = input[0].split(/\s+/).map(Number);
const crossSignals = input.slice(1).map(line => line.split(/\s+/).map(Number));


const top = 0b1000
const bottom = 0b0100
const left = 0b0010
const right = 0b0001


const SIGNAL_LIST = [
    // 1
    {
        from: left,
        to: top | right | bottom,
    },
    // 2
    {
        from: bottom,
        to : top | left | right
    },
    // 3
    {
        from: right,
        to: top | bottom | left,
    },
    // 4
    {
        from: top,
        to: bottom | left | right,
    },
    // 5
    {
        from: left,
        to: top | right,
    },
    // 6
    {
        from: bottom,
        to: top | left,
    },
    // 7
    {
        from: right,
        to: bottom | left,
    },
    // 8
    {
        from: top,
        to: bottom | right,
    },
    // 9
    {
        from: left,
        to: bottom | right,
    },
    // 10
    {
        from: bottom,
        to: top | right,
    },
    // 11
    {
        from: right,
        to: top | left
    },
    // 12
    {
        from: top,
        to: bottom | left,
    }
]


const set = new Set()
// 교차로 번호, 진입 위치, 시간
const carPosition = [0, bottom, 0]
let count = 0


function canMoveTo(signal, direction) {
    return (SIGNAL_LIST[signal].to & direction) > 0;
}


function canMoveInDirection(number, direction) {
    const checks = {
        [bottom]: () => (number + N) < N ** 2,
        [top]: () => (number - N) >= 0,
        [right]: () => (number % N) !== (N - 1),
        [left]: () => (number % N) !== 0,
    };


    return checks[direction] ? checks[direction]() : false;
}


const stack = [carPosition]
function dfs() {
    while (stack.length > 0) {
        const [currentCrossRoad, from, t] = stack.pop()
        set.add(currentCrossRoad)
        const signalLength = crossSignals[currentCrossRoad].length
        const signal = crossSignals[currentCrossRoad][t % signalLength] - 1


        // 시간 다 되었으면 해당 경로 탐색 멈추기
        if (t === T) {
            continue
        }


        if (from === SIGNAL_LIST[signal].from) {
            if (canMoveTo(signal, top) && canMoveInDirection(currentCrossRoad, top)) {
                stack.push([currentCrossRoad - N, bottom, t + 1])
            }
            if (canMoveTo(signal, bottom) && canMoveInDirection(currentCrossRoad, bottom)) {
                stack.push([currentCrossRoad + N, top, t + 1])
            }
            if (canMoveTo(signal, left) && canMoveInDirection(currentCrossRoad, left)) {
                stack.push([currentCrossRoad - 1, right, t + 1])
            }
            if (canMoveTo(signal, right) && canMoveInDirection(currentCrossRoad, right)) {
                stack.push([currentCrossRoad + 1, left, t + 1])
            }
        }


    }
}


dfs(0)
console.log(set.size)


/*
# 입력 분석
N, T는 100이하. ㅇㅋ
N은 정사각형 길이, T는 시간


# 문제 분석
T초 동안 이동을 한 차량이 통과하는 교차로를 기록
막힌 것도 기록
시작 조차 못하는 경우에는 그냥 시작 지점 하나만 끝.
중복은 X. 12개의 교차로가 있는데 12개를 중복으로 순회해도 12가


# 설계
신호에는 최대 4개의 방향 (상 하 좌 우)
각 신호 별로 일단 기록
예) 상 - 0b1000, 하 - 0b0100, 좌 - 0b0010, 우 - 0b0001
예) 신호 1 - 0b1101. [신호1, 신호2, 신호3, ...]


탐색 방법은 DFS, BFS.
DFS의 경우 JS 엔진의 스택 크기를 고려해야함. 최대 깊이는 100(T)으로 제한 되어있으니,
원시 타입만 적게 사용한다면 크게 부담은 없을 것으로 보임.
DFS로 일단 진행


최대한 함수 내 원시 값 없애기
DFS는 재귀호출마다 전역 T 증가, 그냥 stack을?


신호 선택은 (T + 1) mod 신호 개수






 */