본문 바로가기

Algorithm

 (252)
[백준] 9466 : 팀 프로젝트 JAVA 풀이 뭔가 풀릴 듯 안 풀려서 결국 구글링의 힘을 빌렸다. 학생들이 선택한 학생번호를 저장할 int 배열, 각 학생들의 팀 배정이 완료됐는지 확인하는 boolean 배열, 한 바퀴를 돌았는지(=두 번째 방문한 건지) 확인하는 boolean 배열이 필요하다. import java.io.*; import java.util.*; public class Main{ static boolean[] visit, done; static int[] arr; // 완성된 팀의 개수 static int cnt; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(Sys..
[백준] 1167 : 트리의 지름 JAVA 풀이 11725번 트리의 지름 문제에서 입력방식만 달라진 문제였다. import java.io.*; import java.util.*; public class Main { static class Node{ int idx; int cnt; Node(int idx, int cnt){ this.idx = idx; this.cnt = cnt; } } // 정점의 개수 static int v; // 최대인 거리 static int max = 0; // 루트노드에서 가장 멀리 떨어진 정점 static int max_idx = 0; // 정점을 방문했는지 검사하는 배열 static boolean[] visit; // 트리를 저장할 노드들의 어레이리스트 배열을 생성 static ArrayList[] list; public ..
[백준] 1967 : 트리의 지름 JAVA 풀이 모든 노드에 대해서 dfs를 수행하는 방법과, 루트 노드를 기준으로 dfs를 수행해서 가중치가 가장 큰 노드를 찾고, 그 노드부터 다시 dfs를 수행하는 두 가지의 방법으로 풀어보았다. 코드는 크게 다를 게 없지만 실행시간에서 큰 차이가 났다. 전자는 dfs를 2번만 수행하면 되지만 후자는 N-1번 수행해야 하니 당연하다. import java.io.*; import java.util.*; public class Main { static class Node{ int idx; int cnt; Node(int idx, int cnt){ this.idx = idx; this.cnt = cnt; } } static boolean[] visit; static ArrayList[] list; static int m..
[백준] 11725 : 트리의 부모 찾기 JAVA 풀이 import java.io.*; import java.util.*; public class Main { static class Node{ int data; Node left; Node right; Node(int data){ this.data = data; } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); // 양방향그래프 ArrayList list = new ArrayList(); for(int i=0;i
[백준] 1991 : 트리 순회 JAVA 풀이 import java.io.*; import java.util.*; public class Main { static class Node{ char data; Node left; Node right; Node(char data){ this.data = data; } } static int N; static Node[] arr; public static void main(String[] args)throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; N = Integer.parseInt(br.readLine()); // 노드의 배열 생성 arr = new Nod..
[백준] 2146 : 다리 만들기 JAVA 풀이 1. 각각의 섬에 번호를 붙인다. 2. 각 섬에서 bfs를 수행해 다른 섬으로 가는 다리를 구해서 짧은 것으로 업데이트한다. import java.io.*; import java.util.*; public class Main { // 지도의 크기 static int N; // 섬에 붙일 번호 // 0은 바다, 1은 섬이니 2부터 static int landNum = 2; static int[][] map; static boolean[][] visit; // 가장 짧은 다리의 길이 static int answer = Integer.MAX_VALUE; // 방향 배열 static int[] dx = {0,0,-1,1}; static int[] dy = {1,-1,0,0}; static class Node{ ..
[백준] 2178 : 미로 탐색 JAVA 풀이 최단 거리를 구하는 문제는 bfs를 사용하기 import java.io.*; import java.util.*; public class Main { static class Point{ int x; int y; Point(int x, int y){ this.x = x; this.y = y; } } // 상하좌우로 이동할 때 사용할 방향배열 static int[] dx = {0,0,-1,1}; static int[] dy = {1,-1,0,0}; static int[][] graph; static boolean[][] visit; static int N; static int M; static Queue queue = new LinkedList(); public static void main(String[] ..
[백준] 7569 : 토마토 JAVA 풀이 7576번과 같은 토마토 문제인데 이번엔 3차원이다. 크게 다를 건 없었지만 이래저래...배열의 인덱스에서 실수를 많이 했다. import java.io.*; import java.util.*; public class Main { // 토마토 클래스 static class Tomato{ int z; int x; int y; // 생성자 Tomato(int z, int x, int y){ this.z=z; this.x=x; this.y=y; } } // 위 아래 왼쪽 오른쪽 위 아래 static int[] dz = {1,-1,0,0,0,0}; static int[] dx = {0,0,-1,1,0,0}; static int[] dy = {0,0,0,0,1,-1}; static int M; static int..

티스토리툴바