[백준] 2564 경비원

1. 문제

www.acmicpc.net/problem/2564

2564번: 경비원

 

 

2. 접근방법

맵을 만들어서 현재 위치부터 bfs돌리면서 상점을 만나면 거리를 result에 계속 더해주는 식으로 풀었다.

 

가로와 세로의 길이가 주어지기 때문에 맵 크기는 map[세로+1][가로+1]로 지정해준다.

그리고 맵의 테두리가 갈 수 있는 길임을 알려주려고 1로 채워 넣었다.

그리고 상점의 위치에는 2를 넣어준다.

상점의 위치는 동서남북 위치에 거리를 잘 계산하면 된다.

 

이제 내 위치부터 시작해서 bfs로 돌며 상점을 만나면 지금까지의 dist만큼 result에 더하고 모든 상점을 만나면 종료한다

 

3. 풀이

1. 맵 만들어서 테두리에 1넣고 상점 위치에 2 넣기

2. 내 위치부터 bfs를 돌리며 상점을 만나면 지금까지 dist만큼 result에 더하기

3. 모든 상점을 만나면 끝내고 result 출력

 

4. 자바 코드

package Silver;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class P2564경비원 {
	static int G,S;
	static int dr[] = {1,-1,0,0};
	static int dc[] = {0,0,1,-1};
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		G = Integer.parseInt(st.nextToken());// 가로
		S = Integer.parseInt(st.nextToken());// 세로

		int map[][] = new int[S+1][G+1];
		boolean visited[][] = new boolean[S+1][G+1];
		for (int i = 0; i < S+1; i++) {
			map[i][0] = 1;
			map[i][G] = 1;
		}
		for (int i = 0; i < G+1; i++) {
			map[0][i] = 1;
			map[S][i] = 1;
		}
		int N = Integer.parseInt(br.readLine());
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int direct = Integer.parseInt(st.nextToken());
			int dist = Integer.parseInt(st.nextToken());
			Point xy = makexy(direct, dist);
			map[xy.x][xy.y] = 2;
		}
		
		
		st = new StringTokenizer(br.readLine());
		Point me = makexy(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		visited[me.x][me.y] = true;
		int result = 0;
		Queue<Point> que = new LinkedList<Point>();
		que.add(me);
		que.add(new Point(-1, -1));
		int dist = 1;
		int cnt = 0;
		gg:while (true) {
			Point now = que.poll();
			if (now.x == -1) {
				dist++;
				if(que.isEmpty())
					break;
				que.add(new Point(-1,-1));
			}
			
			for(int i = 0 ; i < 4 ;i++) {
				int row = now.x+ dr[i];
				int col = now.y+ dc[i];
				if(row<0 || col<0 || row>= S+1 || col>=G+1)
					continue;
				if(map[row][col] == 0)
					continue;
				if(visited[row][col])
					continue;
				
				visited[row][col] = true;
				if(map[row][col] == 2) {
					result+=dist;
					if(++cnt == N)
						break gg;
				}
				que.offer(new Point(row,col));
			}
		}
		System.out.println(result);

	}
	static Point makexy(int direct,int dist) {
		if(direct == 1) 
			return new Point(0,dist);
		
		else if(direct == 2)
			return new Point(S,dist);
		
		else if(direct == 3) 
			return new Point(dist,0);
		
		else if(direct == 4)
			return new Point(dist,G);
		return null;
	}

}

5. 마치며

처음엔 bfs안쓰고 공식을 만들어서 풀어보려 했는데 생각보다 신경써줘야 하는 부분이 많길래 그냥 맵만들어서 bfs로 풀어버렸다.