CS/알고리즘17 백준 2110번 : 공유기 설치 문제를 보고 이해하는데 오래 걸리고, 힌트를 받았음에도 도통 모르겠어서 답을 찾아봤다. 많이 나온 답을 보고 해석한 내용이다. import java.io.*; import java.util.Arrays; public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] line = br.readLine().split(" "); int n = Integer.parseInt(line[0]); int c = Integer.parseInt(line[1]); int[] arr = new in.. 2021. 3. 26. 백준 2178번 : 미로탐색 미로 탐색은 대표 그래프 문제 중 하나이다. 최단 경로를 찾기 위해서 가장 작은 값으로 바꿔나가는 방식으로 생각했다. 예시를 봤을 때에는 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 은 1 0 9 10 11 12 2 0 8 0 12 0 3 0 7 0 13 0 4 5 6 0 14 15 이런 식으로 채워나가면 되겠다고 생각해서 dfs로 구현을 했다. 하지만, dfs 로 구현했을 때 시간 초과가 계속 떴다. dfs 는 최단경로를 찾기엔 적합한 방법이 아니기 때문이다. 일단 해를 찾으면 끝나는 dfs의 특성상 최단경로라는 최적의 해를 구할 수 없을지도 모른다. 밑의 글에 아주 잘 설명되어 있다. www.acmicpc.net/board/view/25832 라는 걸 극복하기.. 2021. 3. 23. 백준 2606번: 바이러스 1번 컴퓨터와 연결된 컴퓨터들의 개수를 구하는 문제이다. 위의 예시의 4번과 7번 컴퓨터처럼, 동떨어진 컴퓨터를 제외한 컴퓨터의 개수를 구하면 된다. 즉, 1번 컴퓨터에서 갈 수 있는 컴퓨터들을 표시해준 후에, 해당 컴퓨터 개수를 출력하도록 한다. package bakjoon2606.virus; import java.util.Scanner; public class Main { static int[][] arr; static boolean[] visited; static int n; public static void main(String args[]) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); int v = sc.nextInt(); arr = ne.. 2021. 3. 20. 백준 3184번 : 양 1. #으로 둘러싸인 곳이 우리이다. 2. 우리 안에서 늑대인 v와 o인 양을 비교하는데, 우리 안에 늑대가 많으면 늑대의 수를, 양이 많으면 양의 수를 가져온다. 3. 모든 우리 안에 남은 늑대와 양의 수를 가져온다. 문제를 간단하게 위의 3가지 순서로 표현할 수 있다. 딱 보자마자 bfs로 풀면 되겠다는 생각이 들었다. 1. #이 아니고 ,갔다온 지점이 아니면 그 우리를 확인한다. (BFS 함수를 부른다.) 2. 빈 칸이거나 동물일 경우, 옆에 붙어있는 칸들을 모두 확인해서 우리 안이 맞으면 큐에 넣어준다. - 동시에, 동물일 경우엔 해당 동물의 카운트를 증가시킨다. 3. 해당 우리를 모두 검사했다면, 해당 우리에서 점령한 동물의 수를 카운트해준다. import java.util.LinkedList;.. 2021. 3. 20. 이전 1 2 3 4 5 다음
