boj
-
BOJ 11657 [타임머신]알고리즘 풀이/수학 2021. 3. 19. 22:50
BOJ 11657 : www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 처음에 queue에 넣어서 bfs처럼 풀어보려고 시도했으나, cycle을 알아낼 마땅한 방법이 떠오르지 않아 재귀 형식으로 바꿨다. key point는 재귀함수 내의 if문이다. 현재 재귀호출하면서 방문한 적 없는가? 현재 재귀 내에서 방문한 적이 없더라도, 이전에 방문했을 때 저장된 값(arr)보다 적은 시간이 걸리는가? 이 두..
-
BOJ 9184 [신나는 함수 실행]알고리즘 풀이/BFS(너비 우선 탐색) 2021. 3. 7. 23:03
BOJ 신나는 함수 실행 : www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 신나지 않은 함수 실행이다. 메모이제이션을 사용해 풀었다. 배열 인덱스에 50을 더한 이유는 마이너스도 있으니깐,, 밑에 코드는 +50때문에 눈이 좀 피곤할 수도 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44..
-
BOJ 17836 [공주님을 구해라!]알고리즘 풀이/BFS(너비 우선 탐색) 2021. 3. 7. 23:00
BOJ 공주님을 구해라! : www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 간단한 BFS 문제이다. 키포인트는 방문배열(visit)를 3차원으로 설정했다. visited[3][3][0] => 그람 없이 (3, 3)을 방문한 경우 visited[3][3][1] => 그람을 가지고 (3, 3)을 방문한 경우 그람을 획득하면, 해당 node가 그람을 가지도록 체크해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ..
-
BOJ 17141 [연구소 2]알고리즘 풀이/BFS(너비 우선 탐색) 2021. 3. 4. 23:08
BOJ 연구소 2 : www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 옛날에 연구소는 풀어봤는데, 2탄도 있는줄 몰랐다. 나의 풀이 방법은 다음과 같다. 바이러스를 놓을 수 있는 구역을 먼저 체크해 vector에 담아놓는다. 브루트 포스를 이용해 바이러스를 놓는 모든 경우의 수를 체크한다. BFS로 바이러스를 확산시켜본다. 제출하니 420ms나 걸린다... 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24..