[JavaScript] 2025 프로그래머스 코드챌린지 1차 예선 - 지게차와 크레인

Q. 문제

 

A 회사의 물류창고에는 알파벳 대문자로 종류를 구분하는 컨테이너가 세로로 n 줄, 가로로 m줄 총 n x m개 놓여 있습니다. 특정 종류 컨테이너의 출고 요청이 들어올 때마다 지게차로 창고에서 접근이 가능한 해당 종류의 컨테이너를 모두 꺼냅니다. 접근이 가능한 컨테이너란 4면 중 적어도 1면이 창고 외부와 연결된 컨테이너를 말합니다.

최근 이 물류 창고에서 창고 외부와 연결되지 않은 컨테이너도 꺼낼 수 있도록 크레인을 도입했습니다. 크레인을 사용하면 요청된 종류의 모든 컨테이너를 꺼냅니다.

 

위 그림처럼 세로로 4줄, 가로로 5줄이 놓인 창고를 예로 들어보겠습니다. 이때 "A", "BB", "A" 순서대로 해당 종류의 컨테이너 출고 요청이 들어왔다고 가정하겠습니다. “A”처럼 알파벳 하나로만 출고 요청이 들어올 경우 지게차를 사용해 출고 요청이 들어온 순간 접근 가능한 컨테이너를 꺼냅니다. "BB"처럼 같은 알파벳이 두 번 반복된 경우는 크레인을 사용해 요청된 종류의 모든 컨테이너를 꺼냅니다.

위 그림처럼 컨테이너가 꺼내져 3번의 출고 요청 이후 남은 컨테이너는 11개입니다. 두 번째 요청은 크레인을 활용해 모든 B 컨테이너를 꺼냈음을 유의해 주세요. 세 번째 요청이 들어왔을 때 2행 2열의 A 컨테이너만 접근이 가능하고 2행 3열의 A 컨테이너는 접근이 불가능했음을 유의해 주세요.

처음 물류창고에 놓인 컨테이너의 정보를 담은 1차원 문자열 배열 storage와 출고할 컨테이너의 종류와 출고방법을 요청 순서대로 담은 1차원 문자열 배열 requests가 매개변수로 주어집니다. 이때 모든 요청을 순서대로 완료한 후 남은 컨테이너의 수를 return 하도록 solution 함수를 완성해 주세요.

 

* 문제해결의 흐름

1. 원형의 storage에서 위아래양옆을 ''로 감싸기

2. BFS로 1에서 만든 2차원 배열 탐색

3. 최종적으로 arr에서 남아 있는 알파벳의 개수를 계산하여 반환

 

* BFS

1. 방문 여부를 체크할 visit 배열을 생성

2. BFS 탐색을 위한 큐를 생성하고 (0,0)에서 탐색 시작

3. 큐에서 노드를 하나씩 꺼내면서 네 방향(dx, dy)으로 이동

4. 이동한 위치가 유효하고, 방문하지 않았다면 다음 조건을 확인

• request[0]와 같은 문자를 찾으면 history에 좌표를 기록
• request가 1글자인 경우 빈 문자열('')이면 탐색 지속
• request가 2글자인 경우 무조건 탐색 지속

5. 탐색이 끝난 후, history에 저장된 위치의 문자를 ''로 변경하여 제거

 

 

A. 풀이

function solution(storage, requests) {
    var answer = 0;
    
    let n = storage.length;  //행개수
    let m = storage[0].length;  //열개수
    
    //storage 위 아래 양 옆이 ''으로 채워진 배열 arr 생성
    let arr = Array.from({ length: n + 2 }, () => Array(m + 2).fill(''));
    
    //기존 배열을 가운데에 복사
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            arr[i + 1][j + 1] = storage[i][j];
        }
    }
    
    //request bfs
    for(let request of requests){
        bfs(arr, request, n + 2, m + 2)
    }

    //arr에 남은 알파벳 개수 출력
    for(let a of arr){
        answer += a.filter(v => v !== '').length;
    }
    return answer;
}

//위 아래 왼쪽 오른쪽 좌표
const dx = [0,0,-1,1];
const dy = [-1,1,0,0]


function bfs(arr, request, n, m){
    //방문한 컨테이너 확인용 array, false로 초기화
    let visit = Array.from({length : n}, () => Array.from({length : m}, () => false));
    
    visit[0][0] = true  //첫번째 노드 방문
    
    let queue = [[0,0]];  //queue에 넣기

    let history = new Set();  //제거할 좌표를 기록하는 용도

    while(queue.length > 0){  //큐에 남은 노드(컨테이너)가 있다면
        const [x, y] = queue.shift();  //FIFO 노드 빼기

        for(let i = 0; i < 4; i++){  //4방향 확인
            const nx = x + dx[i];
            const ny = y + dy[i];
           
            //존재하는 index + 방문한 적 없는 노드
            if(0 <= nx && nx < n && 0 <= ny && ny < m && !visit[nx][ny]){
                //request가 컨테이너의 알파벳과 동일하다면
                if(request[0] === arr[nx][ny]){
                    //좌표 저장
                    history.add([nx, ny]);
                }
                
                //str의 길이가 1이고(bfs 탐색이 필요함) 현재 노드가 빈 문자열을 가졌을 경우
                if(request.length === 1 && arr[nx][ny] === ''){
                    //방문 true
                    visit[nx][ny] = true;
                    queue.push([nx,ny])  //queue에 넣기
                } else if(request.length === 2){  //str의 길이가 2이면
                    //방문 true
                    visit[nx][ny] = true;
                    queue.push([nx,ny])  //queue에 넣기
                }
            }
        }
    }
    
    //좌표가 기록된 노드 알파벳 빼기
    history.forEach(([x, y]) => {
        arr[x][y] = '';
    });
}