문제https://www.acmicpc.net/problem/3190 풀이뱀의 이동 매커니즘을 큐를 이용해 뱀의 이동 경로를 저장하고 이를 이용해 뱀의 길이 및 뱀의 위치를 계산한다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e.split(' '));const N = +input.shift()[0];const apple = +input.shift()[0];const applePos = input.splice(0, apple).map(e => e.map(Numbe..
코딩 테스트
문제https://www.acmicpc.net/problem/16234 풀이이 문제는 BFS를 학습하기 위해 풀어본 문제이며 이 문제를 통해 BFS를 조금 알기 시작했다.... 문제에서는 각 칸마다 연합을 연결할 수 있는 나라인지 확인한 뒤 계속 인접 칸으로 이동해야 한다. 이러한 풀이 방식에서 인접 노드 탐색을 진행하는 BFS를 적용해야한다. bfs 함수를 실행하는 이중 for문은 각 칸마다 연합을 만들 수 있는지 검증하는 경우를 구현하기위해 사용했고, 해당 노드가 방문했던 노드임을 나타내는 visited 배열을 생성했으며 이 배열을 bfs 함수에 전달해 함수 내부에서 방문 여부를 확인해 방문 하지 않고, 함수에서는 상하좌우 방향의 노드와 현 위치의 노드 간의 차이가 문제에서 주어진 범위 안에 있다면 ..
문제https://www.acmicpc.net/problem/14502 풀이이 문제는 BFS를 이용해 풀이했다. 바이러스가 확장되는 모습이 BFS의 인접한 노드를 모두 방문하는 로직과 비슷했기에 BFS를 이용했다. 하지만 벽을 세우는 로직은 DFS와 비슷하다. 모든 빈 공간 중 3 칸에 벽을 세우는 경우를 구현하는데에 DFS와 같은 모습을 갖는 3개의 for 반복문을 이용해 구현했다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e.split(' ').map(Numb..
문제https://www.acmicpc.net/problem/14890 풀이문제에 주어진 지도를 가로줄을 검증한다. 오른쪽의 블럭이 왼쪽 보다 클 경우는 이전까지의 평지의 길이를 비교해 경사로를 놓을 수 있으면 넘어가고, 왼쪽블럭이 더 큰 경우는 평지의 길이에서 미리 경사로 설치에 필요한 길이를 빼준다. 이 부분에 대해 설명하자면, 뒤에 평지가 나오면 더해지기 때문에 놓을 수 있다면 하나씩 늘어나 양수가 되지만 놓을 수 없다면(더 크거나 작은 블럭이 있는 경우) 음수가 되기 때문에 반복문을 탈출한다. 이후 가로 세로를 변경해 한번 더 반복한다. 코드const { link } = require('fs');const input = require('fs') .readFileSync(process.platfo..
문제https://www.acmicpc.net/problem/15686 풀이이 문제는 완전탐색 문제이며 DFS를 이용해 풀이를 진행했다. 우선 지도에 있는 치킨집의 위치를 담고 있는 배열과 치킨집 위치 배열의 방문 여부를 표시할 배열을 생성한다.위 두 배열을 이용해 문제에서 제공하는 제한할 치킨집의 갯수의 수 만큼 DFS로 검증한다. 이후 각 집 위치에서 치킨집으로 부터의 거리를 측정 후 더해준다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e.split(' ')..
문제https://www.acmicpc.net/problem/15683 풀이이 문제는 완전 탐색으로 풀이하는 구현 문제이다. 감시 카메라는 정해진 방향으로만 감시가 가능하며 감시 구역이 겹치는 것은 가능하지만, 중복된 영역에서 개수 증가는 한개만 가능하다. 또한 카메라 칸은 감시가 불가능 하지만, 그 다음 칸으로의 감시는 가능하다. 이러한 조건만 잘 지키면 구현에 큰 어려움은 없었다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e.split(' ').map(Numb..
