[백준] 18513 샘터 - BFS JAVA

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

18513번: 샘터

 

문제풀이

1. 일반 BFS문제에 방향이 좌우 만 있는 문제입니다.

2. 문제의 조건에 1억 개의 범위가 들어가있는 (-100,000,000 ≤ 샘터의 위치 ≤ 100,000,000) 이 있으므로, 무조건적으로 long을 활용하여 값을 내보내줘야합니다. (int는 21억까지밖에 못함, 여기서 만약 최악의 경우 100,000,000 부터 0까지 모두 더하는 경우가 있을 수 있음)

3. visitedHashSet을 활용하여 방문처리를 합니다. ( (1 ≤ N, K ≤ 100,000) 는 이 범위이지만, 샘터의 위치는 -1억부터 1억이므로 배열형식으로 할경우 쓸데없는 공간을 차지합니다. ) HashSet.contains(Value)를 활용하여 해당 HashSet의 값이 있다면 방문처리 해야합니다.

4. 문제에서 K개의 집만 지을 수 있는데, 이떄 처음에 아래의 집의 개수를 넘어가면 중지시키는 로직을 while(q) 안에 작성하면, 이미 큐에 넣은 상태로 result가 더해지기에 값이 틀립니다. 그러므로 아래의 코드처럼 q에 넣기전에 테스트하여야 합니다. 

if(bfs_success_cnt >= K) continue ;

 

    public static void bfs() {
    	int[] dx = {-1,1};
    	int bfs_success_cnt = 0;
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int x = temp.x;
    		int cnt = temp.cnt;
    		result += cnt; 
    		
    		for(int dir=0; dir<2; dir++) {
    			int nx = x + dx[dir];
    			if(visitedHashSet.contains(nx)) continue; //이미 방문한 적이 있는 위치면 집이나 샘물이 존재하는것이므로  PASS
    			if(bfs_success_cnt >= K) continue ;
    			visitedHashSet.add(nx);
    			q.offer(new Node(nx, cnt + 1));
    			
    			bfs_success_cnt++;
    			
    		}
    	}
    }

 

 

코드

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

public class Main {
	public static int N,K;
	public static int[] map;
	public static Queue<Node> q = new LinkedList<>();
	public static HashSet<Integer> visitedHashSet = new HashSet<>();
	public static long result = 0;
    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());
    	K = Integer.parseInt(st.nextToken());
    	
    	map = new int[N];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		map[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	for(int i=0;i<N;i++) {
    		q.offer(new Node(map[i], 0)); //BFS 시작위치(샘물의 위치에서 시작합니다.)
    		visitedHashSet.add(map[i]); //샘물의 위치를 방문처리시킵니다.
    	}
    	
    	bfs();
    	
    	System.out.println(result);

    	
    }
    
    public static void bfs() {
    	int[] dx = {-1,1};
    	int bfs_success_cnt = 0;
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int x = temp.x;
    		int cnt = temp.cnt;
    		result += cnt; 
    		
    		for(int dir=0; dir<2; dir++) {
    			int nx = x + dx[dir];
    			if(visitedHashSet.contains(nx)) continue; //이미 방문한 적이 있는 위치면 집이나 샘물이 존재하는것이므로  PASS
    			if(bfs_success_cnt >= K) continue ;
    			visitedHashSet.add(nx);
    			q.offer(new Node(nx, cnt + 1));
    			
    			bfs_success_cnt++;
    			
    		}
    	}
    }
}

class Node{
	int x;
	int cnt;
	public Node(int x, int cnt) {
		this.x = x;
		this.cnt = cnt;
	}
}