www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 핵심아이디어 다익스트라를 사용하여 각 정점에서부터의 다른 정점사이의 최단거리를 모두 구하고, 반경범위 내에 있는 노드들의 item개수를 합한 결과값중 가장 큰 값을 반환하면 된다. 이번에도 한번 오답을 받았는데, 그 이유는 visited를 사용하여 방문처리를 해주었기 때문이다. distance에 가장 최소의 값을 업데이트해주어야 하므로, 큰값이 들어간 경우 방문처리를 해버리면 틀릴 수 있기 때문이다. 'use str..

www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 핵심아이디어 bfs와 dp를 적절히 섞어쓰면 되는 문제이다. 예전에 python으로 풀었는데 지금 풀어보려하니 아이디어가 잘 떠오르지 않았다. dp[x][y] 를 x,y좌표까지 도달할때 소모해야 하는 최소 검은방의 개수로 정의하고 bfs를 돌리면된다. 그리고 이때에는 visited를 사용하면 안되는데 그 이유는, 각 방의 최소값을 계속 판단하여 dp값을 업데이트해주어야 하는데, visited으로 초반에 방문처리를 해버..

www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 핵심아이디어 다익스트라로 풀되, 각 지점을 모두 start로 지정하고 다익스트라를 수행한 뒤, start -> X + X -> start 가 가장 max인 거리를 찾으면된다. python에서는 우선순위 큐로 heap을 썼지만, 자바스크립트에는 해당기능이 없어서 일반 큐로 구현하였는데, 간당간당하게 통과했다! 다익스트라용 우선순위큐를 만들어놓아야 할 것 같다.. 'use strict..

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 핵심 아이디어 bfs를 사용하는 문제이다. 기존 NxN 보드에서 사용하는 것과 달린 일직선에서 적용한다는 점만 다르며, +1, -1, *2 되는 지점을 큐에 넣어서 탐색하면된다. "use strict"; const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, outp..

www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 핵심 아이디어 간단한 bfs문제이다. 적록색약일때와 아닐때를 분기 하여 bfs 큐에 넣는 조건으로 사용하면 된다. 적록색약일때 => B/G는 같은 색으로 취급 아닐때 => 각각 다른 색깔로 취급 'use strict'; const { DH_NOT_SUITABLE_GENERATOR } = require('constants'); const readline = require('readline'); const ..

'use strict'; const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const solution = function (input) { const T = parseInt(input.shift()); let [m, n, k] = [-1, -1, -1]; let visited = []; let farm = []; let points = []; let ans = ''; let cnt = 0; const direction = [ [-1, 0], [1, 0], [0, -1], [0, 1], ]; const isValidPoint = (x..

www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. www.acmicpc.net 핵심 아이디어 dfs/bfs 방식으로 풀 수 있는 문제이고 입력 크기가 작기에 dfs로 풀어도 상관없다. dfs는 재귀적으로 더이상 탐색할 노드가 없을 때 재귀를 탈출하게 되는데, 그 점을 이용하여 재귀를 탈출할때마다 방문했던 수를 배열에 추가해주고 출력하면된다. 'use strict'; const readline = require('readline'); const rl = readline.createInterfa..

www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 핵심아이디어 전형적인 DFS문제라서 딱히 언급할 것이 없다. 연결된 모든간선에 대해 dfs를 수행하되, 방문처리를 한 노드는 방문하지 않으면 된다. 'use strict'; const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const solut..