[백준] 19238 스타트 택시

1. 문제

www.acmicpc.net/problem/19238

19238번: 스타트 택시

2. 접근방법

 

문제 자체는 그렇게 어렵지 않은 시뮬레이션 문제인데

문제 이해를 잘못해서 삽질을 좀 했다.

 

우선 풀이법은 간단한데

bfs로 가장 가까운 승객을 찾고

그 승객이 가고자 하는 목적지까지

또 bfs로 이동해서 거리를 구하면 된다.

 

처음 문제를 풀 때 한 승객의 목적지가 다른 승객의 위치가 될 수 있다는 것을 모르고

 

맵 하나에 승객들의 위치와 도착지의 위치를 다 넣어 뒀다가 한 번 갈아 엎었다..

 

그래서 목적지를 저장하는 방법으로

승객의 위치에 그 승객의 목적지 row*100 + col을 키값으로 저장해두는 방식을 사용했다.

 

단 키값을 저장해두는 방식으로 할때

맵의 index를 0 부터 시작하게 했다면

목적지가 0,0 이나 0,1이라면 승객의 위치에 키값 0과 1이 들어가 문제가 발생할 수 있다.

맵을 1부터 시작하게 하던지 키값에 변화를 주던지 하여야 할 것 이다.

 

나머지는 시키는데로 시뮬을 구현하면 되겠다.

3. 자바 코드

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 Main {
	static int N, M, Fuel, map[][];
	static Point me, goal;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		Fuel = Integer.parseInt(st.nextToken());
		map = new int[N+1][N+1];

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		st = new StringTokenizer(br.readLine());
		me = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		for (int i = 2; i < M + 2; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int gx = Integer.parseInt(st.nextToken());
			int gy = Integer.parseInt(st.nextToken());
			map[x][y] = gx*100+gy;
		}

		int people = 0;
		boolean flag = true;
		while (true) {
			int num = findSome();
			if (num == -1) {
				flag = false;
				break;
			}
			goal = new Point(num/100,num%100);
		
			if (!findGoal()) {
				flag = false;
				break;
			}
			people++;
			if (people == M)
				break;
		}
		System.out.println(flag ? Fuel : -1);

	}

	static int dr[] = { 1, -1, 0, 0 };
	static int dc[] = { 0, 0, 1, -1 };
	static int findSome() { // what == 0? 가까운승객 : 도착지
		int dist = 0;
		Queue<Point> que = new LinkedList<Point>();
		que.offer(new Point(me.x, me.y));
		boolean visited[][] = new boolean[N+1][N+1];
		visited[me.x][me.y] = true;
		Point man = null;
		while (!que.isEmpty()) {
			int size = que.size();
			for (int s = 0; s < size; s++) {
				Point now = que.poll();
				if (map[now.x][now.y] > 1) {
					if (man == null) {
						man = new Point(now.x, now.y);
					}else {
						if(now.x < man.x) {
							man = new Point(now.x, now.y);
						}else if(now.x == man.x && now.y < man.y) {
							man = new Point(now.x, now.y);
						}
					}
				}
				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 > N || col > N)
						continue;
					if (visited[row][col])
						continue;
					if (map[row][col] == 1)
						continue;
					visited[row][col] = true;
					que.offer(new Point(row, col));
				}
			}
			if(man != null) {
				Fuel -= dist;
				if(Fuel <0)
					return -1;
				me.x = man.x;
				me.y = man.y;
				int thenum =map[man.x][man.y]; 
				map[man.x][man.y] = 0;
				return thenum;
			}
			dist++;
		}
		return -1;
	}
	static boolean findGoal() {
		int dist = 0;
		Queue<Point> que = new LinkedList<Point>();
		que.offer(new Point(me.x, me.y));
		boolean visited[][] = new boolean[N+1][N+1];
		visited[me.x][me.y] = true;
		while(!que.isEmpty()) {
			int size = que.size();
			for(int s = 0 ; s < size ; s++) {
				Point now = que.poll();
				if(goal.x == now.x && goal.y == now.y) {
					Fuel -= dist;
					if(Fuel <0)
						return false;
					me.x = now.x;
					me.y = now.y;
					Fuel += dist*2;
					return true;
				}
				
				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 > N || col > N)
						continue;
					if (visited[row][col])
						continue;
					if (map[row][col] == 1)
						continue;
					visited[row][col] = true;
					que.offer(new Point(row, col));
				}
				
			}
			dist++;
			
		}
		return false;
	}

}

4. 마치며

문제 이해를 잘못해서 삽질하느라 정말 힘들었다...

알고리즘을 풀면 코딩실력 뿐만 아니라 독해능력도 같이 느는 것 같아 너무 좋다.