고민의 흔적

26번 DFS와 BFS

내가 떠올린 풀이 해설

DFS와 BFS를 구현할 수 있는지 물어보는 기본 문제이다.

문제 조건에서 작은 번호의 노드부터 탐색한다고 했으므로 인접 노드를 오름차순으로 정렬한 후 구현한다. 또한 DFS가 끝났을 떼 방문 배열을 초기화해준다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1260 {
	static ArrayList<Integer> arr[];
	static boolean visited[];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int v = Integer.parseInt(st.nextToken());
		
		arr = new ArrayList[n + 1];
		for(int i = 1; i <= n; i++) {
			arr[i] = new ArrayList<>();
		}
		
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int e = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			arr[e].add(s);
			arr[s].add(e);
		}
		for(int i = 1; i <= n; i++) {
			Collections.sort(arr[i]);
		}
		visited = new boolean[n + 1];
		DFS(v);
		System.out.println();
		visited = new boolean[n + 1];
		BFS(v);
	}
	private static void BFS(int i) {
		Queue<Integer> que = new LinkedList<>();
		que.add(i);
		visited[i] = true;
		
		while(!que.isEmpty()) {
			int now = que.poll();
			System.out.print(now + " ");
			for(int b : arr[now]) {
				if(!visited[b]) {
					visited[b] = true;
					que.add(b);
				}
			}
		}
	}
	private static void DFS(int i) {
		System.out.print(i + " ");
		visited[i] = true;
		for(int b : arr[i]) {
			if(!visited[b]) {
				DFS(b);
			}
		}
	}
}

27번 미로 탐색

내가 떠올린 풀이 해설

N, M의 최대 크기가 100으로 매우 작기 때문에 DFS나 BFS의 시간제한은 생각하지 않아도 되는 문제다.

지나야 하는 칸수의 최솟값을 구하는 문제이므로 BFS로 풀었다. 상하좌우를 탐색하면서 칸의 숫자가 1이면서 아직 방문하지 않았다면 큐에 삽입한다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek2178 {
	static int arr[][];
	static boolean visited[][];
	static int []dx = {1, 0, -1, 0};
	static int []dy = {0, 1, 0, -1};
	static int n,m;
	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());
		
		arr = new int[n][m];
		visited = new boolean[n][m];
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			String line = st.nextToken();
			for(int j = 0; j < m; j++) {
				arr[i][j] = Integer.parseInt(line.substring(j, j + 1));
			}
		}
		BFS(0,0);
		System.out.println(arr[n - 1][m - 1]);
	}

	private static void BFS(int i, int j) {
		Queue<int[]> que = new LinkedList<>();
		que.offer(new int[]{i, j});
		visited[i][j] = true;
		while(!que.isEmpty()) {
			int now[] = que.poll();
			
			for(int k = 0; k < 4; k++) {
				int x = now[0] + dx[k];
				int y = now[1] + dy[k];
				if(x >= 0 && x < n && y >= 0 && y < m) {
					if(arr[x][y] != 0 && !visited[x][y]) {
						visited[x][y] = true;
						arr[x][y] = arr[now[0]][now[1]] + 1;
						que.add(new int[] {x,y});
					}
				}
			}
		}
	}
}

문제점

자연스럽게 Integer.parseInt(st.nextToken())으로 코드를 작성했는데 오류가 발생했다. 왜 오류가 났는지 찾다가 입력 예제가 띄어쓰기로 되어있는 게 아니라 한 줄로 붙어었다는것을 발견했다... que.add 할 때 {x, y}를 add 해야 되는데 {i, j}를 add를 해서 계속 답이 안 나왔다. 이번 문제 오류를 찾느라 한참 걸렸다.

28번 문제 트리의 지름

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1167 {
	static boolean visited[];
	static int[] distance;
	static ArrayList<Edge> []arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		arr = new ArrayList[n + 1];
		for(int i = 1; i <= n; i++) {
			arr[i] = new ArrayList<Edge>();
		}
		for(int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			while(true) {
				int e = Integer.parseInt(st.nextToken());
				if(e == -1) {
					break;
				}
				int v = Integer.parseInt(st.nextToken());
				arr[s].add(new Edge(e, v));
			}
		}
		distance = new int[n + 1];
		visited = new boolean[n + 1];
		BFS(1);
		int max = 1;
		for(int i = 2; i <= n; i++) {
			if(distance[max] < distance[i]) {
				max = i;
			}
		}
		distance = new int[n + 1];
		visited = new boolean[n + 1];
		BFS(max);
		Arrays.sort(distance);
		System.out.println(distance[n]);
	}
	private static void BFS(int index) {
		Queue<Integer> que = new LinkedList<>();
		que.add(index);
		visited[index] = true;
		while(!que.isEmpty()) {
			int now = que.poll();
			for(Edge i : arr[now]) {
				int e = i.e;
				int v = i.value;
				if(!visited[e]) {
					visited[e] = true;
					que.add(e);
					distance[e] = distance[now] + v;
				}
			}
		}	
	}
}
class Edge {
	int e;
	int value;
	public Edge(int e, int value) {
		this.e = e;
		this.value = value;
	}
}

문제점

문제를 고민해봤지만 풀지 못했다. 아직 골드까지 풀기는 부족한 실력인 것 같다.

오늘의 회고

오늘은 책에 있는 문제를 풀었습니다. 책이 실전 대비 책이라 그런지 어려운 문제들이 포함되어있습니다.ㅠㅠ  안 풀린다고 좌절하지 말고 천천히 기본부터 익혀 나가겠습니다. 내일은 그동안 학습했던 문제들 복습하고 정리하는 시간과 시간이 되면 오늘 보단 쉬운 문제를 풀겠습니다.