[Goorm] 현대모비스 예선 주차시스템 JavaScript

반응형

[Goorm] 현대모비스 예선 주차시스템

---

접근

• BFS

---

풀이

자바스크립트로 코딩테스트를 쳐야 하기에 자바스크립트 공부를 시작했다. 문법이 익숙하지 않아 자바로 하는 것처럼 완성한 후 GPT의 도움을 받아 자바스크립트 스타일로 가공(?)을 받았다. 2차원 좌표가 주어지고 칸들을 순회하며 값을 구해야 하기에 BFS를 이용해 탐색을 시도했다.

let N = 0;
let M = 0;
let parking = [];

for await (const line of rl) {
	let str = line.split(" ").map(Number);

	if (str.length === 2) {
		N = str[0];	
		M = str[1];
        } 
	else {
		parking.push(str);
	}

	// 입력이 끝나면 처리
	if (N !== 0 && parking.length === N) {
		let maxScore = findMaxScore(N, M, parking);
		console.log(maxScore);
		rl.close();
	}
}

단순히 자바스크립트의 문법만 보고 풀려하니 비동기 처리와 입력을 받고 출력을 하고 하는 부분이 자바와 너무 다른 느낌이라 많이 헤매었다. realine으로 읽어 들이는 것을 for await 문 안에서 한 줄씩 다뤄지는 거 같길래 입력받는 값을 처리해 배열에 넣어주고 마지막 입력을 다 받은 뒤 따로 만든 함수를 이용해 값을 구해 출력한 뒤 readline을 닫아 주었다.

 

function findMaxScore(N, M, parking) {
    let directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    let visited = new Array(N).fill().map(() => new Array(M).fill(false));

값을 구할 함수를 선언했다. 탐색을 할 때 좌표 값을 변경해 줄 방향 배열과 중복체크를 위한 방문 확인 배열이다. 자바에서 늘  dx = {0, 0, -1, 1}와 dy = {1, -1 ,0, 0} 배열로 따로 선언하여 사용했었는데 GPT가 그냥 저렇게 만들어 주길래 놔뒀다.

function isValid(x, y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }

진행 방향 체크용 함수이다. 이 부분도 원래 함수가 아니라 if문 안에서 체크를 해주었는데 GPT가 지저분해 보이는지 함수로 따로 빼버렸다.

function bfs(startX, startY) {
        let queue = [[startX, startY]];
        let score = 0;
        let count0 = 0;
        let count2 = 0;

        if (parking[startX][startY] === 0) {
            count0++;
        } else if (parking[startX][startY] === 2) {
            count2++;
        }

        visited[startX][startY] = true;

bfs를 구현하는 함수이다. 큐로 사용할 배열과 점수를 저장할 변수, 0과 2가 몇 개인지 셀 변수들과 초기화이다. 자바스크립트는 배열을 가지고 큐와 스택의 기능을 동시에 사용 가능한 게 편리한 거 같다.

while (queue.length > 0) {
	let [x, y] = queue.shift();

	for (let dir of directions) {
		let nx = x + dir[0];
		let ny = y + dir[1];

		if (isValid(nx, ny) && !visited[nx][ny] && parking[nx][ny] !== 1) {
			visited[nx][ny] = true;
			queue.push([nx, ny]);

			if (parking[nx][ny] === 0) {
				count0++;
			} else if (parking[nx][ny] === 2) {
				count2++;
			}
		}
	}
}

진행 방향으로 나아가며 탐색해 준다 . 진행 방향이 왔던 곳이거나 1이면 탐색을 종료하게 된다. 탐색을 마치게 되면 1로 둘러 쌓인 즉 0과 2로 이루어진 영역의 점수가 구해진다.

	score = count0  - count2 * 2;
return score;

0이 있는 칸은 1점이고 2가 있는 칸은 -2 점이기 때문에 점수를 계산해 반환한다.

 let maxScore = 0;

for (let i = 0; i < N; i++) {
	for (let j = 0; j < M; j++) {
		if (!visited[i][j] && parking[i][j] !== 1) {
			let areaScore = bfs(i, j);
			if (areaScore > maxScore) {
				maxScore = areaScore;
			}
		}
	}
}

return maxScore;

이제 배열을 순회하며 영역의 점수를 계산하고 최댓값을 구해주는 부분이다. 방문했던 곳이라면 이미 영역의 점수가 구해졌기 때문에 넘어가고 방문하지 않은 영역들의 넓이를 구해 현재 최댓값과 비교하여 최신화한다.

---

전체 코드

// Run by Node.js
const readline = require('readline');

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

    let N = 0;
    let M = 0;
    let parking = [];

    for await (const line of rl) {
        let str = line.split(" ").map(Number);

        if (str.length === 2) {
            N = str[0];
            M = str[1];
        } else {
            parking.push(str);
        }

        // 입력이 끝나면 처리
        if (N !== 0 && parking.length === N) {
            let maxScore = findMaxScore(N, M, parking);
            console.log(maxScore);
            rl.close();
        }
    }
})();

function findMaxScore(N, M, parking) {
    let directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    let visited = new Array(N).fill().map(() => new Array(M).fill(false));

    function isValid(x, y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }

    function bfs(startX, startY) {
        let queue = [[startX, startY]];
        let score = 0;
        let count0 = 0;
        let count2 = 0;

        if (parking[startX][startY] === 0) {
            count0++;
        } else if (parking[startX][startY] === 2) {
            count2++;
        }

        visited[startX][startY] = true;

        while (queue.length > 0) {
            let [x, y] = queue.shift();

            for (let dir of directions) {
                let nx = x + dir[0];
                let ny = y + dir[1];

                if (isValid(nx, ny) && !visited[nx][ny] && parking[nx][ny] !== 1) {
                    visited[nx][ny] = true;
                    queue.push([nx, ny]);

                    if (parking[nx][ny] === 0) {
                        count0++;
                    } else if (parking[nx][ny] === 2) {
                        count2++;
                    }
                }
            }
        }

        score = count0  - count2 * 2;
        return score;
    }

    let maxScore = 0;

    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            if (!visited[i][j] && parking[i][j] !== 1) {
                let areaScore = bfs(i, j);
                if (areaScore > maxScore) {
                    maxScore = areaScore;
                }
            }
        }
    }

    return maxScore;
}

자바스크립트로 푼 첫 문제였는데 익숙하지 않다 보니 자바스크립트의 편리한 기능들이 아직은 너무 불편하다. 자료형을 내가 선택해 변수를 선언하지 않는다는 게 익숙하지 않고 오히려 더 혼란스러운 느낌이다.