BOJ - 샘터 18513번 (JAVA)

❓ 문제 - 백준 샘터 18513번 - JAVA 풀이법

 

출처 

(https://www.acmicpc.net/problem/18513)

18513번: 샘터

 

 

 

📝 문제해결법

1. 이 문제는 BFS로 해결했다.

• 샘터 위치를 큐에 넣고 BFS를 돌려서 가장 가까운 곳의 집을 다 위치시키면 그 때의 거리를 출력하면 된다.
• visited을 체크하기 위해서 HashSet을 이용했으며 배열로 했을 때 메모리 부분이나 더 오버헤드가 크다.
• 큐를 돌면서 방문하지 않은 곳에 집을 위치 시키며 그 때 위치시킨 집의 갯수와 거리를 누적해서 더하면서 만약 위치시킨 집의 갯수와 k개가 같으면 return해서 누적한 거리를 출력한다.
• 범위는 샘터의 범위만 주어졌으므로 집을 위치시키는 범위에 제한은 없으므로 이것을 주의해서 풀어야 한다.

 

2. 느낀점

• 예전에 모의 역량 A형에서 일직선상에서 bfs로 위치시키는 문제를 만났을 때 어떻게 접근할지 몰라서 못 풀었는데 이 문제를 만나서 어떻게 접근할지 배울 수 있었다.

 

 

💻 소스코드 (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Main {
	public static int n, k;
	public static Set<Integer> visited;
	public static class Node {
		int x;
		int dist;
		public Node(int x, int dist) {
			this.x = x;
			this.dist = dist;
		}
	}
	public static Queue<Node> q;
	public static int[] dx = {-1, 1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] data = br.readLine().split(" ");
		n = Integer.parseInt(data[0]);
		k = Integer.parseInt(data[1]);
		q = new LinkedList<>();
		visited = new HashSet<Integer>();
		data = br.readLine().split(" ");
		for(int i=0;i<n;i++) {
			int x = Integer.parseInt(data[i]);
			q.add(new Node(x, 0));
			visited.add(x);
		}
		
		long ans = bfs();
		System.out.println(ans);
	}
	
	public static long bfs() {
		long dist = 0;
		int cnt = 0;
		while(!q.isEmpty()) {
			Node node = q.poll();
			for(int d=0;d<2;d++) {
				int nx = node.x + dx[d];
				if(visited.contains(nx)) continue;
				
				dist += (node.dist+1);
				cnt++;
				visited.add(nx);
				
				if(cnt == k) return dist;
				q.add(new Node(nx, node.dist+1));
			}
		}
		
		return dist;
	}
	
	

}