위의 예제들은 쉽게 답이 나올 수 있다. 그러나 어려운 반례를 찾아보았는데 예제 입력 6 30 19 0 -1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 -1 0 0 0 0 0 ..

모든 노드를 탐색한다면 DFS와 BFS 모두 상관없겠지만 주어진 문제는 두 지점간의 최단경로를 탐색해야 하기 때문에 BFS를 사용하는 문제이다. BFS는 가중치가 없는 간선간의 최단거리를 보장할 수 있다. BFS가 최단거리를 보장하는 이유는 다음과 같다. BFS는 자신과 바로 연결되어 있는 노드들을 큐에 넣는다. 그리고 큐는 FIFO에 따라서 가장 먼저 들어온 것들을 먼저 처리한다. 이 두가지 특성이 결합되어 시작지점으로부터 간선의 수가 작은 곳부터 먼저 처리되게 된다. 따라서 간선 2개로 도달할 수 있는 노드가 간선 1개로 도달할 수 있는 노드보다 큐에 먼저 들어오는 일은 발생하지 않으므로 최단거리를 보장할 수 있다. 주어진 문제는 1,1에서 시작하여 N,M까지의 최소 칸 수를 구해야 하는데, 즉 (1..

이 문제는 DFS와 BFS 방법 모두 풀 수 있다. 상하좌우로만 이동할 수 있다고 했으므로 상하좌우로 붙어있어야 연결되었다고 볼 수 있다. 일단 주어진 자료를 모두 배열에 담는다. 그리고 배열을 이중for문을 통해 행과 열을 돌면서 (0행0열부터 0행 1열, 0행 2열 ...) 집이 있다면(값이 1이라면) 그리고 방문한 적이 없다면 DFS 혹은 BFS를 실행하면 된다. 이 때, 탐색이 한 번 끝나게 되면 한 단지가 만들어졌다고 볼 수 있다. 왜냐하면 기본적인 DFS와 BFS도 연결되어있는 그래프를 가지고 순서대로 탐색하기 때문이다. 기본적인 DFS와 BFS에서는 다음 탐색 대상은 현재 탐색 대상인 정점의 인접한 정점을 탐색했었는데 위의 경우에서는 어떻게 다음 탐색 대상을 정할 수 있을까? 바로 moveR..

문제를 풀기 위한 아이디어 1번 컴퓨터부터 시작하여 경로를 거치게 되는 정점을 모두 구하는 문제이다. DFS 방법으로 풀어도 되고 BFS 방법으로 풀어도 무방하다. 예제의 경우 DFS로 풀면 1→2→3→5→6 순으로 거치게 되고, BFS로 풀면 1→2→5→3→6 으로 거치게 된다. 내가 작성한 코드 1. DFS로 푼 방법 let fs = require("fs"); let input = fs.readFileSync("/dev/stdin").toString().split("\n"); const vertexNumber = Number(input[0]); // 컴퓨터의 수 : 7 const edgeNumber = Number(input[1]); // 간선의 수 : 6 input.shift(); input.shi..

문제를 풀기 위한 아이디어 시간 제한은 2초이므로 대략 2억번의 연산까지 허용된다고 생각하고 풀어야 한다. 정확한 답을 구해내려면 완전탐색 유형으로 접근하여 모든 경우의 수를 다 따져본 후 가장 최선의 답을 고르면 되겠지만, 입력이 최대 10만이므로 이 방법은 효율적이지 않다. 따라서 위의 문제를 풀기 위해서는 현재 상황에서 지금 당장 좋은 것만 고르는 그리디 알고리즘으로 풀어야 한다. 그리디 알고리즘이 언제나 최적의 해를 보장하는 것은 아니지만 많은 문제에 대한 해를 보다 효율적으로 구해낼 수 있다. 위의 문제는 그리디 알고리즘의 대표적인 유형 중 하나인 활동선택 문제에 해당한다. * 활동 선택 문제 : 한 번에 하나의 활동만 처리할 수 있는 하나의 강의실에서 제안된 활동들 중 가장 많은 활동을 처리할..

내가 작성한 코드(자바스크립트) let fs = require("fs"); let input = fs.readFileSync("/dev/stdin").toString().split("\n"); const N = Number(input[0]); input.shift(); const result = []; const array = new Array(8001); array.fill(0); for (let i = 0; i < N; i++) { let index = Number(input[i]) + 4000; array[index]++; } for (let j = 0; j < array.length; j++) { if (array[j] !== 0) { for (let k = 0; k < array[j]; k++)..