문제https://www.acmicpc.net/problem/9205 풀이최대 20병이 들어가는 맥주 한 박스를 들고 출발하여 50m마다 맥주를 한 병씩 마시면서 가야 할 때, 상근이네 집에서 페스티벌에 갈 수 있으면 "happy"를, 그렇지 않으면 "sad"를 출력한다.편의점 개수 + 3(편의점 개수, 상근이 집 좌표, 페스티벌 좌표 입력) 씩 인덱스를 증가시키면서 테스트 케이스를 입력받는다.한 박스에 20병을 넣을 수 있고, 50m마다 맥주 한 병을 마셔야 하기 때문에 최대 이동할 수 있는 거리는 20x50=1000m이다. 따라서 서 맥주를 채울 수 있는 편의점까지 이동할 때, 또는 도착지인 페스티벌 좌표까지 이동할 때 거리가 1000m가 넘어가면 갈 수 없다.편의점을 무조건 순서대로 방문하는 것이 ..
문제https://www.acmicpc.net/problem/16946 풀이모든 1에서 BFS를 돌면 (NM)^2으로 시간초과벽 주변의 0 묶음의 개수를 더하면 이동할 수 있는 영역이다.따라서 이동 가능한 영역인 0 묶음의 개수를 세어 주변 벽인 1에 더해준다.모듈러 연산의 분배법칙을 생각하고 매번 나눠주는 경우, board 원본 배열의 벽을 증가시키다 10의 배수가 되는 경우 0이 되어 벽으로 인식하지 못하는 문제가 생기므로 유의해야 한다. 시간복잡도: O(NM)class Queue { constructor() { this.data = []; this.head = 0; this.tail = 0; } push(item) { this.data[this.tail++] = item;..
문제https://www.acmicpc.net/problem/15683 15683번: 감시스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감www.acmicpc.net 풀이각 cctv 위치에서 4방향으로 돌면서 cctv 유형에 따라 가능한 칸까지 탐색한다.시작점은 정해져 있기 때문에 DFS는 index만 넘겨준다.탐색(watch)은 cctv 유형에 따라 확인할 방향 dirToWatch를 정하고, 해당 방향으로 벽을 만날 때까지 이동한다. board 자체가 DFS를 돌면서 계속 변경되기 때문에 DFS 전후로 board를 깊은 복사 하여 사용한다. con..
문제 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 풀이 치즈의 바깥 가장자리 부분만 돌면서 값을 변경해야 하는데, 이를 위해 치즈(1)이 아닌 바깥쪽(0)을 BFS 탐색한다. 0이면 BFS로 계속 탐색하고, 1이면 nodes에 넣고 탐색이 끝난 후에 0으로 변경해 준다. - [0, 0]에서 시작해 bfs - [nx, ny]가 0이면 bfs 대상 -> queue.push() - [nx, ny]가 1이면 녹일 대상 -> 0으로 변경 - 이 과정을 치즈가 없을 때까..
문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 0은 빈 칸, 1은 벽, 2는 바이러스가 있고, 바이러스는 4방향으로 퍼져나갈 수 있다. 이때 벽을 3개 세운 뒤 바이러스가 퍼질 수 없는 영역인 안전 영역의 최대 크기를 찾는 문제이다. 1. 0인 구간 가운데 3개 고르기 (3중 for문 또는 DFS) 2. 2인 경우 큐에 넣어서 BFS 돌리면서 2로 바꾸고 3. 전체 탐색하면서 0인 곳 개수 세서 최댓값 찾기 이때 주의해야할 점은 3개를 선정하고..
문제 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 문제를 읽고 숫자고르기와 같이 각 요소에서 DFS 탐색을 해야 한다는 걸 알 수 있었다. 주어진 입력으로 양방향 그래프를 만들고, 각 1~N에서 각각 방문 표시 배열(ch)을 이용한 DFS를 한다. 이때 flag 변수를 사용하여 연결된 노드가 5개가 나오는 경우 return 해서 DFS를 종료한다. 또한 flag가 1인 경우, 즉 A, B, C, D, E가 존재하는 경우, for문을 종료한다. flag가 1이면 1을 아니면 0을 출력한다. 처음에는 DFS에서 연결된 개수를 반환해주고, 다 돌..
문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 이전에 풀었던 방식과 유사하지만 nodes라는 하나의 배열을 이용해 인구 이동을 조금 더 간단하게 구현하였다. 2중 for문으로 각각의 땅에서 BFS를 돌고 이동 가능한 경우 nodes 배열에 담아둔다. BFS가 끝나면 nodes 배열에 담긴 좌표들은 인구 이동을 해준다. nodes 배열에 자기 자신만 담긴 경우(nodes.length === 1) 이동하지 못했다는 의미이..
문제 https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 풀이 const fs = require("fs"); const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; let [N, ...nums] = fs .readFileSync(filePath) .toString() .trim() .split("\n") .map(Number); const answer ..
