Untitled1.class

문제 링크: https://www.acmicpc.net/problem/2623풀이일단 위상 정렬 문제이다.그리고 방향 그래프의 사이클 여부를 탐색해야 한다.사이클이 있을 때는 0을, 이외에는 위상 정렬 수행 결과를 출력한다. 사이클 여부 탐지에는 DFS(Stack)을 사용했는데,모든 node에서 DFS 탐색을 시작해 보고, 만약 탐색 도중 시작점으로 돌아온다면 사이클로 처리했다. 위상 정렬은 indegree가 0인 node부터 시작해,이어지는 node들의 indegree 테이블 정보를 갱신하며 StringBuilder에 추가했다.작성한 코드import java.util.*;import java.io.*;class Main { static StringBuilder sb=new StringBuilder..

문제 링크: https://www.acmicpc.net/problem/2250풀이그림 보고중위순회구나~ 했는데 .. 노드 정보를 유동적으로 관리 못한 게 NPE의 원인 ㅠ.ㅠ무슨 말이냐 함은 .. root가 항상 1번 node는 아니라는 것.그리고 input이 꼭 노드의 번호 순서대로 들어오지 않는 것,. 그래서 List 형태로 graph 정보를 관리해줬다. ㅎ.ㅎ작성한 코드import java.util.*;import java.io.*;class Main { static class Node{ int left; int right; public Node(int left, int right){ this.left=left; th..

문제 링크: https://www.acmicpc.net/problem/15681풀이서브 트리에 속한 노드의 카운트를 세는 게 요점이다.graph를 이용해 도출한 childInfo를 기반으로 calc 함수를 이용해, DFS로 카운트해 준다.작성한 코드import java.util.*;import java.io.*;class Main { static List> graph=new ArrayList(); static List> childInfo=new ArrayList(); static int[] childCount, parent; static int N; public static void main(String[] args) throws Exception { Buffere..

문제 링크: https://www.acmicpc.net/problem/48031차: 11.111트 실패: 7:30~8:302트 실패: 8:30~9:302차: 11.13힌트 보고 풀음~! 사이클 탐지가 문제였음.풀이사이클 탐지가 관건인 문제.DFS를 사용했다.특정 노드부터 탐색을 시작해,다음으로 방문할 노드가 이미 방문한 next(바로 직전) 노드라면양방향 그래프이기 때문에 사이클 처리하지 않는다.그러나, 직전 노드가 아닌 다른 노드로 이어진다면 사이클 처리한다.아래 dfs 메소드는 디버깅을 위해 boolean 타입을 return하도록 작성했는데, void로 해도 상관 없다.작성한 코드import java.util.*;import java.io.*;class Main { static boolean[]..

문제 링크: https://www.acmicpc.net/problem/1707이분 그래프 알고리즘을 사용했다.아니이게무슨~감도안잡혔다. 결론: 풀이 참조함작성한 코드2가지 색상을 이용한다.한 그래프 정보를 입력 받아서, 노드들의 색상 정보를 갱신한다. (BFS)특정 노드의 색상과 이 노드와 인접한 노드들의 색상이 다르면 이분 그래프, 이외는 탈락이다.import java.util.*;import java.io.*;class Main { static int[] color; static List> graph; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader..

문제 링크: https://www.acmicpc.net/problem/11403풀이플로이드 워셜을 사용했다.입력 받을 때, INF 값을 연산에 어긋나지 않으면서도, int 범위 내인 101로 지정했다.플로이드 워셜 후 원소가 101이면 도달 불가(0), 이외 1 이상이면 도달 가능(1)으로 값을 수정했다.작성한 코드import java.util.*;import java.io.*;class Main { static int[][] matrix; static int N; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(..

문제 링크: https://www.acmicpc.net/problem/5567풀이인접 리스트를 사용해 BFS 했다.반례 케이스:31 32 3이 케이스에서 답이 2려면, 2 → 3 뿐만 아니라 3 → 2도 연결해 주어야 한다. (양방향 연결)작성한 코드import java.util.*;import java.io.*;class Main { static class Node{ int number; int depth; public Node(int number, int depth){ this.number=number; this.depth=depth; } @Override public String ..

문제 링크: https://www.acmicpc.net/problem/1655풀이힙 구성에는 priority queue를 사용했다.pqLeft는 최대 힙, pqRight는 최소 힙이다.매번 최대 힙의 peek 값이 중앙값이라는 가정 하에, (pqLeft.size()==pqRight.size()일 때, pqLeft에 offer한다)최대 힙(중앙값 이하), 최소 힙(중앙값 초과)를 이용한다.pqLeft의 size와 pqRight의 size가 같을 때, pqLeft에 offer한다.만약 pqLeft의 peek값이 pqRight의 peek값보다 크다면(원소 정렬이 어긋남), peek 원소를 switch한다.매번 pqLeft.peek() 값을 출력한다.작성한 코드import java.util.*;import ja..