[백준] 15591 MooTube, java

https://www.acmicpc.net/problem/15591

15591번: MooTube (Silver)

문제 이해

 

문제를 꼼꼼히 읽어야겠다는 생각을 다시 한번 하게 된 문제입니다. 일단 주어진 문제의 레벨은 골드 5였기 때문에 그렇게 겁먹지 않고 접근을 했지만 결국 다른 풀이를 보고 나서야 풀어낼 수 있었던 문제입니다.

 

모든 지점에서의 모든 유사도를 이차원 int 배열에 표시를 해두고, Q를 통해서 주어진 위치에서 k 이상의 유사도를 세어보자라고 풀이를 시작했습니다. 결론적으로 해당 풀이는 기가 막힌 시간 초과를 뱉어내었습니다. 저는 이 풀이를 진행할 때에는 결국 모든 유사도를 다 구하기 때문에 DFS, BFS 관계가 없겠구나 생각을 하여 DFS를 이용해 진행했습니다.

 

일단 시간 초과가 나타났기 때문에 생각할 수 있는 최적화를 진행했습니다. arr[a][b]의 유사도는 곧 arr [b][a]의 유사도이므로 이도 표시 해주고, 유사도가 정해진 위치의 개수를 세어줘야 하나 같이 요런 저런 생각을 해보고 시도해 보았지만 모두 다를 바 없는 시간초과였습니다.

 

해당 문제에 시간을 많이 쓰고 있어서 결국 풀이를 찾아봤는데, 조금은 이해가 가지 않는 설명이었지만, 천천히 곱씹어보니 확실히 시간을 줄일 수 있는 풀이였습니다. 해당 풀이는 코드를 통해서 설명하겠습니다.

 

package com.baekjoon.gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main_BJ_15591_G1_MooTube {

	static int N, Q, k; //문제에서 주어지는 N과 Q, 그리고 사용할 k
	static HashMap<Integer, ArrayList<Integer>> map; //key 위치에 직접 연결 된 value 위치들
	static int[][] arr; //이차원 배열을 이용해 표현한 해당 i, j 사이의 유사도

	//디버깅을 하기 위해 만든 Print() 함수
	static void Print(){
		StringBuilder sb = new StringBuilder();

		for (int i = 1; i < N+1; i++) {
			for (int j = 1; j < N+1; j++) {
				sb.append(arr[i][j] + " ");
			}
			sb.append("\n");
		}

		System.out.println(sb.toString().trim());
	}

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		//주어진 데이터를 입력 받아 줍니다.
		N = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken());
		arr = new int[N+1][N+1];
		map = new HashMap<>();

		//N-1 라인 만큼 입력을 받아 arr에 유사도를 표시해줍니다.
		//유사도는 단방향이 아니기 때문에 양쪽으로 표시해 주었습니다.
		for (int i = 0; i < N-1; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
			arr[s][e] = v;
			arr[e][s] = v;

			//직접 연결된 두 좌표에 대해서는 주어진 유사도보다 작은 유사도가 주어질 수 없기에
			//빠르게 판단하기 위해 map에 담아줍니다.
			if(!map.containsKey(s)){
				map.put(s, new ArrayList<>());
				map.get(s).add(e);
			} else {
				map.get(s).add(e);
			}

			if(!map.containsKey(e)){
				map.put(e, new ArrayList<>());
				map.get(e).add(s);
			} else {
				map.get(e).add(s);
			}
		}

		StringBuilder sb = new StringBuilder();

		//이제 문제 Q를 직접 받아들이며 개수를 세어줄겁니다.
		for (int i = 0; i < Q; i++) {

			//문제에서 주어지는 k와 기준 영상 p!
			st = new StringTokenizer(br.readLine());
			k = Integer.parseInt(st.nextToken());
			int p = Integer.parseInt(st.nextToken());

			//bfs에 사용될 q를 선언해주고, 시작점이 될 영상 p를 입력해줍니다.
			Queue<Integer> q = new LinkedList<>();
			q.add(p);

			//유사도가 k이상이라면 개수에 포함되어야 함, 그 개수를 세어줄 cnt 입니다.
			int cnt = 0;

			//양방향 관계이기에 무한루프가 돌 수 있으니까 방문처리를 해주어 반복을 멈춰줄
			//visited 입니다.
			boolean[] visited = new boolean[N+1];

			//bfs 진행!
			while(!q.isEmpty()){

				//q에서 좌표 하나를 꺼내줍니다!
				int now = q.poll();
				visited[now] = true; //방문처리!
				if(now != p) cnt++;  //시작할 때는 본인의 위치이나 얘는 cnt에 들어가지 않음 그 외에는 cnt++;

				//현재 위치(영상)에서 갈 수 있는 곳들의 리스트를 가져옵니다!
				ArrayList<Integer> nowArr = map.get(now);

				//현재 영상과 연결되어 있는 좌표를 꺼내주고
				//현재 영상과 다음 영상의 유사도가 k보다 클 때만! q에 담아줍니다.
				//k보다 작다면 이를 통해서 연결된 모든 영상들은 k유사도 미만의 값을 가지기 때문에 어차피
				//cnt에 포함될 수 없기에 담을 필요가 없습니다!!
				for (int j = 0; j < nowArr.size(); j++) {
					int nowEnd = nowArr.get(j);
					if(arr[now][nowEnd] >= k && !visited[nowEnd]) q.add(nowEnd);
				}
			}

			//위를 통해서 세어진 cnt를 sb에 추가해줍니다.
			sb.append(cnt+"\n");
		}

		//sb 출력을 통해서 결과!!
		System.out.println(sb.toString().trim());
	}
}

 

후기

오랜만에 집중해서 문제를 푼 것 같은데, 오롯이 나만의 힘으로 풀지는 못했지만 머리를 쓰는 시간은 꽤 상쾌하고 뿌듯했던 것 같습니다!