[구현] 백준 2564번 경비원 - JAVA

 

 

설탕배달2가 생각보다 빠르게 풀린 것 같아 내가 못풀고 쟁여놨던 경비원 문제를 풀어보았다.

그동안 프로젝트하면서 함수를 장난아니게 만들었더니 함수를 이용해 차근차근 푸는 능력이 생겼나보다.

잘 해결해내었다. 좀.. 비효율적인 코드인 것 같지만... ^^

아무튼 시작!

 

 

---

1. 출처

---

 

2564번: 경비원

 

 

 

이것도 3달 전엔 못풀었던 문제다...ㅎㅎ

알고를 한동안 쉬다가 오니 머리가 리프레쉬라도 되었나...^^

 

 

---

2. 설계

---

 

 

일단 문제 자체 이해는 쉽다.

경비원 X가 (동/서/남/북) 위치에서 가게(1,2,3)들에 접근할 때 최단 거리를 구하고, 각 최단거리의 총 합을 구하면 되는 문제이다.

여기서 주의할 점은 가게의 정보가 2가지 숫자로 주어지는데, 이것이 좌표가 아니라, (동/서/남/북) 방향 정보와 좌/우에서 얼마만큼 떨어졌냐의 정보라는 것이다.

 

 

일단 나는 2가지 측면에서 생각하여 문제를 풀려고 했다.

1) 동근이의 위치가 (동/서/남/북)일 때

2) 가게의 위치가 (동/서/남/북)일 때

 

예를 들면, 동근이의 위치가 동쪽에서 2만큼 떨어진 거리에 있을 때 1번 가게가 동쪽에 있다면 서로 같은 방향에 있는 것이다.

이 때는 둘의 y좌표는 같은데, x좌표가 다르므로 동근이와 1번가게의 x좌표를 빼고, 절대값을 해준 것이 최단 거리이다.

 

글로 이해하기 어렵다면, 코드로 확인해보자!

 

 

이 코드는 동근이가 남쪽방향일 때 가게들이 각각 동/서/남/북 일 때 어떻게 거리를 계산할 것인지 써 둔 함수이다.

//동근이가 남
	public static void SOUTH(int idx) {
		Store cur_store = storeList.get(idx);
		Store dong = storeList.get(count);
		
		//1:북 / 2:남 / 3:서 / 4:동 
		
		//동쪽 가게 == 오른쪽 방향 
		if(cur_store.direction==4) {
			minDistance.add((width - dong.y) + (height - cur_store.x));
		}
		
		
		//서쪽 가게 == 왼쪽 방향 
		else if(cur_store.direction==3) {
			minDistance.add(dong.y+(height-cur_store.x));
		}
		
		
		//남쪽 가게 == 같은 방향 
		else if(cur_store.direction==2) {
			minDistance.add(Math.abs(dong.y-cur_store.y));
		}
		
		
		//북쪽 가게 == 맞은편 방향 
		else if(cur_store.direction==1) {
			int distance1 = dong.y+height+cur_store.y; //왼쪽 
			int distance2 = (width-dong.y)+height+(width-cur_store.y); //오른쪽  
			minDistance.add(Math.min(distance1,distance2));
		}
	}

 

1) 우선 같은 방향일 때에는 남쪽이기 때문에 y좌표만 서로 다르다. 때문에 두 값을 빼준 것에 절대값이 최소경로이다.

Math.abs(3-8);

2) 가게가 북쪽에 있는 땐 서로 정반대, 맞은편 방향이다. 때문에 동근이가 왼쪽으로 가는 방향과 오른쪽으로 가는 방향 2가지를 고려해줘야 한다.

 

- 왼쪽으로 가는 경우는 순차적으로 [동근이의 y + height + 1번가게의 y]를 지나쳐서 가기 때문에 최단거리가 다음과 같이 나온다.

- 오른쪽으로 가는 경우는 순차적으로 [(width-동근이의 y) + height + (width-1번가게의 y)] 를 지나쳐서 가기 때문에 최단거리가 다음과 같이 나온다.

 

 

3) 가게가 서쪽에 있는 땐 서로 왼쪽 방향이다. 오른쪽을 거쳐서 가는 것 보다 항상 왼쪽방향으로 가는 것이 최소거리가 나온다.

동쪽도 마찬가지다. 오른쪽 방향도, 왼쪽을 거쳐서 가는 것 보다 오른쪽 방향으로 가는 것이 항상 최소거리가 나온다.

 

 

 

이런식으로 맞은편의 있는 경우만 2가지 경우를 고려해주고, 나머지는 그쪽으로 동근이가 움직일 수있게 판을 짜주었다.

 

 

 

 

---

3. 전체코드

---

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	
	static List<Store> storeList=new ArrayList<>();
	static List<Integer> minDistance=new ArrayList<>();
	static int count;
	static int width;
	static int height;
	
	public static class Store{
		int x;
		int y;
		int direction;
		public Store(int x, int y, int direction) {
			super();
			this.x = x;
			this.y = y;
			this.direction = direction;
		}
	}

	public static void main(String[] args) {
		//제한시간 1초 
		//동근이의 위치에 따라 최단 거리가 달라질 것 같음
		Scanner sc = new Scanner(System.in);
		
		width = sc.nextInt();
		height = sc.nextInt();
		
		count = sc.nextInt();
		
		//가게들의 위치 + 동근이의 위치 
		for(int i=0;i<count+1;i++) {
			int direction = sc.nextInt();
			int distance = sc.nextInt();
			
			//1:북 / 2:남 / 3:서 / 4:동 
			//즉, storeList 마지막에는 동근이의 위치가 있는 것 
			if(direction == 1) {
				storeList.add(new Store(0,distance,direction));
			}else if(direction == 2) {
				storeList.add(new Store(5,distance,direction));
			}else if(direction == 3) {
				storeList.add(new Store(distance,0,direction));
			}else if(direction == 4) {
				storeList.add(new Store(distance,5,direction));
			}
			
		}
		
		//입력 받기 끝 
		
		//가게 수대로 최단 거리 구해야함 
		//1:북 / 2:남 / 3:서 / 4:동 
		if(storeList.get(count).direction==1) {
			for(int i=0;i<count;i++) {
				NORTH(i);
			}
		}else if(storeList.get(count).direction==2) {
			for(int i=0;i<count;i++) {
				SOUTH(i);
			}
		}else if(storeList.get(count).direction==3) {
			for(int i=0;i<count;i++) {
				WEST(i);
			}
		}else if(storeList.get(count).direction==4) {
			for(int i=0;i<count;i++) {
				EAST(i);
			}
		}
		
		
		//총합 출력 
		int result = 0;
		for(int i=0;i<count;i++) {
			result += minDistance.get(i);
		}
		
		System.out.println(result);
	}
	
	//동근이가 동
	public static void EAST(int idx) {
		Store cur_store = storeList.get(idx);
		Store dong = storeList.get(count);
		
		//1:북 / 2:남 / 3:서 / 4:동 
		
		//동쪽 가게(?,y) == 같은 방향 
		if(cur_store.direction==4) {
			minDistance.add(Math.abs(cur_store.x-dong.x));
		}
		
		
		//서쪽 가게 == 맞은편 방향 
		else if(cur_store.direction==3) {
			int distance1 = dong.x+width+cur_store.x; //위 
			int distance2 = (height-dong.x)+width+(height-cur_store.x); //아래 
			minDistance.add(Math.min(distance1,distance2));
		}
		
		
		//남쪽 가게 == 아래쪽 방향 
		else if(cur_store.direction==2) {
			minDistance.add((height-dong.x)+(width-cur_store.y));
		}
		
		
		//북쪽 가게 == 위쪽 방향 
		else if(cur_store.direction==1) {
			minDistance.add((dong.x)+(width-cur_store.y));
		}
	}
	
	//동근이가 서
	public static void WEST(int idx) {
		Store cur_store = storeList.get(idx);
		Store dong = storeList.get(count);
		
		//1:북 / 2:남 / 3:서 / 4:동 
		
		//동쪽 가게 == 맞은편 방향 
		if(cur_store.direction==4) {
			int distance1 = dong.x+width+cur_store.x; //위 
			int distance2 = (height-dong.x)+width+(height-cur_store.x); //아래 
			minDistance.add(Math.min(distance1,distance2));
		}
		
		
		//서쪽 가게 == 같은 방향 
		else if(cur_store.direction==3) {
			minDistance.add(Math.abs(cur_store.x-dong.x));
		}
		
		
		//남쪽 가게 == 아래쪽 방향 
		else if(cur_store.direction==2) {
			minDistance.add((height-dong.x)+(cur_store.y));
		}
		
		
		//북쪽 가게 == 위쪽 방향 
		else if(cur_store.direction==1) {
			minDistance.add((dong.x)+(width-cur_store.y));
		}
	}
	
	//동근이가 남
	public static void SOUTH(int idx) {
		Store cur_store = storeList.get(idx);
		Store dong = storeList.get(count);
		
		//1:북 / 2:남 / 3:서 / 4:동 
		
		//동쪽 가게 == 오른쪽 방향 
		if(cur_store.direction==4) {
			minDistance.add((width - dong.y) + (height - cur_store.x));
		}
		
		
		//서쪽 가게 == 왼쪽 방향 
		else if(cur_store.direction==3) {
			minDistance.add(dong.y+(height-cur_store.x));
		}
		
		
		//남쪽 가게 == 같은 방향 
		else if(cur_store.direction==2) {
			minDistance.add(Math.abs(dong.y-cur_store.y));
		}
		
		
		//북쪽 가게 == 맞은편 방향 
		else if(cur_store.direction==1) {
			int distance1 = dong.y+height+cur_store.y; //왼쪽 
			int distance2 = (width-dong.y)+height+(width-cur_store.y); //오른쪽  
			minDistance.add(Math.min(distance1,distance2));
		}
	}
	
	//동근이가 북 
	public static void NORTH(int idx) {
		
		Store cur_store = storeList.get(idx);
		Store dong = storeList.get(count);
		
		//1:북 / 2:남 / 3:서 / 4:동 
		
		//동쪽 가게 == 오른쪽 방향 
		if(cur_store.direction==4) {
			minDistance.add((width - dong.y) + (cur_store.x));
		}
		
		
		//서쪽 가게 == 왼쪽 방향 
		else if(cur_store.direction==3) {
			minDistance.add(dong.y+cur_store.x);
		}
		
		//남쪽 가게 == 맞은편 방향 
		else if(cur_store.direction==2) {
			int distance1 = dong.y+height+cur_store.y; //왼쪽 
			int distance2 = (width-dong.y)+height+(width-cur_store.y); //오른쪽  
			minDistance.add(Math.min(distance1,distance2));
		}
		
		//북쪽 가게 == 같은 방향 
		else if(cur_store.direction==1) {
			minDistance.add(Math.abs(dong.y-cur_store.y));
		}
	}

}

 

설계에 없는 내용으로는 class를 썼다는 것이다. class는 각 가게의 x, y, 방향 정보를 넣어주기 위해 썼다.

그리고 입력으로는 방향정보와 방향에서 어느정도 떨어졌는지 수만 주어지는 데 그것을 이용해 정확한 x, y좌표를 계산하였다.

 

 

코드 자체는 길지만, 동근이의 위치에 따라 하나의 함수만 동작하므로 시간이 그리 오래 걸리지 않는다.

최대 100개의 가게가 입력될 수 있는데,

가게 및 동근이의 위치 입력할 때 100번 > 100개의 가게가 for문을 돌며 함수 진입하여 최소 거리 계산이다.

 

 

 

 

---

역시 구현 문제는 항상 복잡해~

 

끝!