[백준] 11725 - 트리의 부모 찾기 자바

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

 

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

 

예제 입력

7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력

4
6
1
3
1
4

 

풀이 방법

1. 정점이 주어졌기 때문에 인접 리스트를 이용했다.

2. 1번 정점부터 bfs로 정점을 탐색하며 각 정점을 parents 배열의 인덱스로 사용하고, 그 정점의 이전(부모)를 값으로 넣었다.

 

 

내 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_2206 {
	static int N, M, min=Integer.MAX_VALUE;
	static char[][] map;
	
	static class Node{
		int y, x, depth;
		boolean broken;
		
		public Node(int y, int x, int depth, boolean broken) {
			super();
			this.y = y;
			this.x = x;
			this.depth = depth;
			this.broken = broken;
		}
	}
	
	static int[] dy = {-1,1,0,0};
	static int[] dx = {0,0,-1,1};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new char[N][];
		
		for (int i = 0; i < N; i++) {
			map[i] = br.readLine().toCharArray();
		}
		
		Queue<Node> queue = new LinkedList<>();
		boolean[][][] visited = new boolean[N][M][2];
		
		queue.offer(new Node(0,0,1,false));
		visited[0][0][0] = true;
		
		while(!queue.isEmpty()) {
			Node cur = queue.poll();
			
			if(cur.y==N-1 && cur.x==M-1)
				min = Math.min(min, cur.depth);
			
			for (int d = 0; d < 4; d++) {
				int ny = cur.y + dy[d];
				int nx = cur.x + dx[d];
				
				if(ny<0 || ny>=N || nx<0 || nx>=M) continue;
				
				if(map[ny][nx]=='0') {	//벽이 아닐 때
					if(!cur.broken && !visited[ny][nx][0]) { 	//지금까지 부순 벽이 없다면
						queue.offer(new Node(ny,nx,cur.depth+1,false));
						visited[ny][nx][0] = true;
					} 
					else if(cur.broken && !visited[ny][nx][1]) {	//지금까지 부순 벽이 있다면
						queue.offer(new Node(ny,nx,cur.depth+1,true));
						visited[ny][nx][1] = true;
					}
				} else {	//벽일 때
					if(!cur.broken) {	//지금까지 부순 벽이 없다면
						queue.offer(new Node(ny,nx,cur.depth+1,true));
						visited[ny][nx][1] = true;
					}
					
				}
			}
		}

		if(min == Integer.MAX_VALUE)
			System.out.println(-1);
		else
			System.out.println(min);
		
		br.close();

	}
}