pinevienna blog

입력된 트리의 루트를 1이라고 가정한다. 각 노드의 부모를 구하는 문제!! 노드들의 연결 정보를 list에 저장시켜 놓고 재귀함수를 돌며 부모노드를 찾는다.즉, 부모노드 정보를 저장할 parents 변수가 하나 더 필요함 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 import java.io.*; import java.util.ArrayList; import java.util.StringTokenizer; public class BOJ_11725 { static int N; static int[] p..

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다). 지도가 주어질 때, 두 대륙을 연결하는 가장 짧은 다리의 길이를 구하는 문제 먼저 섬끼리 구분을 할 수 있도록 넘버링을 해준다. 넘버링 메서드 makeLand private static void makeLand(int x, int y) { Queue que = new LinkedList(); que.add(new..

토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 보관 후 하루가 지나면, 익은 토마토들의 인접(상하좌우)한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 구하는 문제 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다. 생각보다 어려웠던.. 문제.. 어쩌면 나만 그런 문제.. ? 일(day)수를 구하는 문제이므로 익은 토마토들이 한 번에 큐에 들어가줘야 한다. main public static void main(String[] arg..

N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제 bfs로 푸는 문제다.. 아니 사실 모르겠다.. dfs도 되나? 길을 찾아가며 +1씩 카운팅 해주고, map[N-1][M-1]을 출력해주면 된다. main visited = new boolean[N][M]; visited[0][0] = true; bfs(0, 0); System.out.println(map[N-1][M-1]); 출발점인 (1, 1) 지점에 방문표시를 하고, bfs를 돌려준다. bfs public static void bfs(int x, int y) { Queue qu..

정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 연결된 집의 모임인 단지를 정의하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 문제. * 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선 상에 집이 있는 경우는 연결된 것이 아니다. dfs, bfs 두 가지 방법으로 문제를 풀 수 있다. 비슷비슷한 문제들이 많은데 거의 좌표로 상하좌우의 값을 탐색하기 위해 dx, dy 배열을 만든다. static final int[] dx= {0,0,1,-1}; static final int[] dy = {1,-1,0,0}; 이 문제에선 입력받기 위한 변수들과 방문여부를 체크할 변수 외에 단지 번호를 카운팅 해주기 위한 변수, ..