[BOJ-18513][BFS] 샘터 - Java

문제 바로가기

18513번: 샘터

 

신박한 BFS 문제입니다.

입력으로 들어올 수 있는 샘터의 위치가 무려 -1억~1억임니다.

억소리가 납니다.

import java.io.*;
import java.util.*;

public class Main {
	static int[] dx = {1, -1};																	
	static final int HMIL = 100000000;																

	static class Dir{
		int cur, next;
		Dir(int cur, int next) {
			this.cur = cur; this.next = next;
		}
	}
	
	public static long bfs(int[] spring, int K) {				
		Queue<Dir> q = new LinkedList<>();		
		Set<Integer> dupCheck = new HashSet<>();
		long sum  = 0;
		
		for(int i = 0; i < spring.length; i++) {											
			q.offer(new Dir(spring[i], spring[i]));	
			dupCheck.add(spring[i]);
		}
		
		while(!q.isEmpty()) {		
			Dir cur = q.poll();																		
			
			for(int i = 0; i <2; i++) {																
				Dir next = new Dir(cur.cur, cur.next + dx[i]);																
				if(next.next > HMIL || (-1 * HMIL) > next.next || dupCheck.contains(next.next)) continue;							

				q.offer(next);
				dupCheck.add(next.next);
				sum += Math.abs(next.cur - next.next);																	
				K--;				
				
				if(K == 0) return sum;																		
			}
		}
		return -1;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));						
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(st.nextToken());				
		st = new StringTokenizer(br.readLine(), " ");												
		int[] spring = new int[N];																		
		for(int i = 0; i < N; i++) {
			spring[i] = Integer.parseInt(st.nextToken());							
		}
		
		System.out.println(bfs(spring, K));																		
	}
}

맨 처음에 방문 여부를 체크하는 visited 배열의 크기를 2억만큼 주니 메모리 초과가 떴습니다.

 

문제에 주어진 공간은 일직선이므로 위치 값을 해시셋에 넣어서 중복을 제거(방문 여부 체크) 했습니다.

이렇게 또 하나 배웠습니다...

 

그리고 큐에는 그때그때마다 출발한 샘터의 위치값을 갖고 있도록 해서 불행도를 바로 계산했습니다.

 

근데 문제에서 집을 지을 수 있는 위치 범위가 명시돼 있지 않아서 -1억~1억으로 했을 때 정답이 떴는데, 그 뒤에도 집을 지을 수 있게 한 코드도 정답이 떴네여.. 일단 질문 올려놔씀다...

 

 

 

문제를 풀 때마다 아직 하아아아아아ㅏㅏㅏㅏㅏㅏㄴ참 멀었다고 생각됩니다...

 

화이팅 ㅜㅜ