개발하는 고라니

13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net [Floyd-Warshall or 다익스트라] 나는 플로이드-와샬로 풀었으나, 다익스트라로 푸는 것이 어쩌면 더 적은 시간이 들지도 모르겠다. 다익스트라를 사용한다면 k번의 다익스트라를 수행하게 되니까 말이다. 일반적인 플로이드 와샬 문제처럼 거리의 대한 배열 dist를 i == j일때는 0으로, 아닐때는 INF로 초기화 해놓고, 입력에 따라 dist에 값을 대입한다. for(int i=1; i

10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net [크루스칼 알고리즘] 보통 MST하면 모든 정점이 하나의 덩어리로 연결되는 것을 생각할 수 있는데, 이 문제의 경우 발전소의 개수(k)개의 덩어리로 나뉘어 모든 정점이 연결되었을 때의 합을 출력하는 문제이다. 나는 유니온-파인드 부분을 수정했다. 보통 유니온-파인드는 두 정점 a, b를 받아 더 작은 번호를 부모 노드로 삼는 것이 일반적인데, Set에 발전소의 번호를 넣어두고 1) 두 정점 모두 발전소에 연결되어있지 않다..

16397번: 탈출 첫 번째 줄에 N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), G (0 ≤ G ≤ 99,999)가 공백 하나를 사이에 두고 주어진다. 각각 N은 LED로 표현된 수, T는 버튼을 누를 수 있는 최대 횟수, G는 탈출을 위해 똑같이 www.acmicpc.net [BFS] 문제에서 주어진 B 버튼을 눌렀을 때의 기능을 잘 구현할 수 있다면 어렵지않게 해결할 수 있을 문제. B는 n을 2배로 증가하고 0이 아닌 가장 높은 자릿수의 값을 1 감소시키는 기능이므로 2번의 반복문을 사용하여 해결하였다. static int B(int x){ int result = 0, idx = 10; int[] arr = new int[5]; for(int i=0, k=10000; i

16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net [다익스트라] 오랜만에 다익스트라 알고리즘 문제를 풀어볼까 해서 여유롭게 푸는가 했으나 너무 안일하게 생각했던 문제. 여우는 문제없이 최단거리를 구할 수 있겠는데.... 늑대는 속도가 x2배 일 수도, 0.5배 일 수도 있으므로 조금 고민해보지 않으면 쉽지 않은 문제인 것 같다. 도대체 어떻게 접근해야할지 떠오르질 않아 질문 게시판을 보다가 아 이거구나 하는 질문을 찾았다. 링크는 하단에 공유하도록 한다. ..

17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net [BFS] 우리는 생각해야한다. '그람'을 얻었을 때와 얻지 않았을 때의 visit를. 즉 visit는 3차원 배열로 선언했다. 이동한 횟수 move 또한 3차원 배열로 만들 수 있으나, 그냥 Queue의 원소로 넘겨주었다. 따라서 Queue의 원소에 들어가는 값은 총 4가지이다. static class Point{ int y, x, find, move; public Point(int yy, int xx, int find, int move){ y=..

11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net [다익스트라] 입력으로 출발 정점과 도착 정점이 주어지므로 한 정점에서 모든 정점으로의 최단 거리를 구하면 된다. 이 문제는 무난한 다익스트라 문제같이 보이나, 출발 정점 ~ 도착 정점 최단 거리의 경로를 구해야 한다. 나는 이 과정을 Dijkstra() 내에서 구현하였다. int[] from 라는 배열에 다음 정점을 방문하기 전에 어디서 왔는지에 대한 정보를 적었다. ( from[next] = current ) 아무튼 이건 포스팅..

2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net [DFS] 주어진 배열에서 사이클을 찾아 답을 출력할 배열에 입력하는 것이 목표이다. 나는 기존에 좀 복잡한 방법으로 사이클을 찾고 답을 출력했더니... 시간초과가 발생하였다. 그래서 어떻게 시간을 단축시킬까 하던 도중, 한 블로그를 보고 뒤통수를 맞은 느낌이었다. 너무나 쉬운 코드로 작성한 것을 보고 성찰의 시간을 갖기로 하였다. 블로그의 링크는 하단에 기재한다. 참고한 블로그의 풀이방식은 n회 DFS를 수행하며 DFS를 돌다 다음 정점이 처음 시..

13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net [DFS or BFS] 이런 2차원 배열이 주어지는 탐색문제에서 주로 BFS만 사용했어서 이번엔 DFS로 풀어보았다. 문제의 답을 도출하는 방법은 매우 단순하다. 첫째 줄에서 출발해서 검은 칸이 아닌 상하좌우 흰색 칸을 따라 마지막 줄까지 도달할 수 있는가? static boolean DFS(int y, int x){ if(y == r) return true; visit[y][x] = true; boolean result = f..