For Beginners

MST는 무조건 양방향 그래프다. 양방향 그래프가 주어지면 MST로 풀 수 있는가를 의심하면 된다. 간적크간많프 개인적으로 PQ를 직접 구현할 수 있는 수준이면 prim을, DisjointSet을 구분하는 로직을 잘 짜면 Kruskal을 추천하신다고 하셨다. DIJKSTRA의 경우에는 상황에 따라 양방향/단방향으로 주어지는데 대부분의 시험 문제는 단방향으로 주어지는 경우가 많다.

www.acmicpc.net/problem/14502 벽은 완탐으로 배치하고, 저번에 치즈를 엄하게 DFS로 풀었던게 생각이 나서 BFS 큐 생성하는 로직을 참고하여 BFS로 코드를 만들었다. 벽을 새로 배치할 때마다, 큐에 넣어주어야 하는 바이러스와 맵을 초기화해주어야 한다는 부분이 핵심인것 같다. 메모리 줄이는 방법도 있을것같은데, 일단 구현했다. import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class BOJ_14502_Main { static int N, M, ans; static int[] dx = {-1, 1, 0, 0}; static i..

www.acmicpc.net/problem/2636 이거는 사실 녹일 영역만 큐에 넣어서 풀면 되는데, 큐에 넣는 것이 아직 익숙하지 않아서 완탐 재귀로 풀었다. 공기와 접촉하지 않은 영역이 존재하는 경우, 공기와의 접촉 여부를 위해 영역 계산을 한다. 공기와 접촉한 영역에 대해 치즈를 녹여서 2라는 영역으로 바꾼다음에, 그 다음 턴에서는 -1로 적용될 수있도록 한다. 중간에 치즈를 세는 countOne이라는 메서드를 잘 못 작성해서 오래 헤맸었는데, 팀원들과 코드리뷰를 하다가 발견해서 해결했다. import java.util.Scanner; public class Main { static Scanner sc; static int[][] map; static boolean[][] visited; stat..

www.acmicpc.net/problem/1342 처음에는 중복을 신경써서 풀어야 하는거 아닌가 생각했지만. 중복은 마지막에 제외해주면 되는 것이고, worst의 경우에는 중복이 일어나는 상황이 아니라 모든 문자열이 다 처음 보는 문자인 경우라서, 시간 복잡도에 영향을 주지 않는다는 것을 깨달았다. package boj.day0323; import java.util.Arrays; import java.util.Scanner; public class BOJ_1342_Main { static char[] input; static char[] output; static boolean[] visited; static int ans; public static void main(String[] args) { Sc..