백준 19238 스타트택시

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

BFS 문제중에 난이도가 올라가면 올라갈수록.. 놓치기 쉬운부분은 다음과같다.

BFS로 한방에 다풀어야지 가 아닌 BFS로 탐색을 하여서 해당 문제를 차근차근 풀어나가야지

이다 즉

해당문제의 경우 BFS 로 하나의 자료형을 만들고 그안에 연료값과 여러가지를 계산하고 한번에 이동하자~~ 라고 생각하면 머리가 아파온다..

하지만 좀더 자세히풀어나가면

출발지로부터 승객을 태우려는 위치 계산을 BFS로 사용해서 계산해주고

승객위치에서 도착지까지 거리를 BFS로 탐색해서 계산해주는 시뮬레이션 문제로 보면 좀더 접근이 쉬워진다.

그래서 핵심 로직은 다음과 같다.

1. 현재위치로부터 가장 가까운 승객탐색 (bfs)
2. 승객 선택후 위치 변경 + 연료 계산 (연료 다떨어지면 종료)
3. 현재위치로부터 승객에 목적지 경로 탐색 (bfs)
4. 목적지 도착후 + 연료 계산 (연료 다떨어지면 종료)

1-4 사이클 승객수 만큼 반복하기

코드는 다음과 같다.

import java.util.*;
import java.io.*;


class xyobj{
	int x;
	int y;
	int p;
	public xyobj(int x,int y,int p) {
		this.x=x;
		this.y=y;
		this.p=p;
	}
}


public class 스타트택시 {

	static int n;
	static int m;
	static int l;
	static int[][] array;
	static int[] dx = new int[] {0,0,1,-1};
	static int[] dy = new int[] {1,-1,0,0};
	static LinkedList<xyobj> sl,el;
	
	
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		l = Integer.parseInt(st.nextToken());
		
		array = new int[n][n];
		
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<n;j++) {
				array[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		st = new StringTokenizer(br.readLine());
		
		int fx =  Integer.parseInt(st.nextToken())-1;
		int fy =  Integer.parseInt(st.nextToken())-1;
		
		
		sl = new LinkedList<>();
		el = new LinkedList<>();
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			int sx = Integer.parseInt(st.nextToken())-1;
			int sy = Integer.parseInt(st.nextToken())-1;
			sl.add(new xyobj(sx,sy,0));
			int ex = Integer.parseInt(st.nextToken())-1;
			int ey = Integer.parseInt(st.nextToken())-1;
			el.add(new xyobj(ex,ey,0));
		}
		
		for(int i=0;i<m;i++) {
			
			
			int delindex = -1;
			int cx= 23; int cy =23;
			int minmove= Integer.MAX_VALUE-1;
			// 출발
			for(int j=0;j<sl.size();j++) {
				xyobj cur = sl.get(j);
				int curmove = bfs(fx,fy,cur.x,cur.y);
				
				if(curmove==minmove) { // 최단 거리 중복의 경우
					if(cx==cur.x) { // 행번호 중복인경우
						if(cy>=cur.y) { //열번호가 적은걸 체크
							cx=cur.x;
							cy=cur.y;
							delindex= j;
							minmove= curmove;
						}
					}
					else if(cx>cur.x) { // 행번호가 더 작은경우
						cx=cur.x;
						cy=cur.y;
						delindex= j;
						minmove= curmove;
					}

				}
				else if(curmove<minmove) { // 최단거리 인경우 
					cx=cur.x;
					cy=cur.y;
					delindex= j;
					minmove= curmove;
				}
			}
			
			if(delindex==-1 || l-minmove<0  ) { // 가장 적은 값을 찾지 못햇거나 혹은 이동중 연료가 떨어지는경우 
				l=-1;
				break;
			}
			
			// 가장 최단경로 찾으면 연료 빼주고 지워주기 , fx, fy 옮겨주기
			fx = cx; fy = cy; l = l-minmove;
			sl.remove(delindex);
			
			
			//승객태우고 도착지로
			xyobj cur = el.get(delindex);
			int curmove = bfs(fx,fy,cur.x,cur.y);
			
			//중간에 연료 끝나는경우 
			if(curmove>l) {
				l=-1;
				break;
			}
			
			fx = cur.x; fy = cur.y; l = l+curmove;
			el.remove(delindex);
			
		}
		System.out.println(l);
		
	}
	
	static int bfs(int sx,int sy,int ex, int ey) {
		int answer = Integer.MAX_VALUE;
		int[][] visited = new int[n][n];
		visited[sx][sy] = 1;
		Queue<xyobj> q = new LinkedList<>();
		q.add(new xyobj(sx,sy,0));
		while(!q.isEmpty()) {
			xyobj cur = q.poll();
			
			if(cur.x==ex && cur.y==ey) {
				answer = cur.p;
				break;
			}
			
			for(int i=0;i<4;i++) {
				int nx =cur.x+dx[i];
				int ny =cur.y+dy[i];
				if(nx<0 || nx >=n || ny<0 || ny>=n) continue;
				if(visited[nx][ny]==1 || array[nx][ny]==1) continue;
				visited[nx][ny]=1;
				q.add(new xyobj(nx,ny,cur.p+1));

			}
		}

		return answer;
	}
	

}

한번 틀렸는데 이유는..

손님 경로가 중복인경우에 행 -> 열 순서로 선택한다는 기준을 따로 안넣어서 틀렸는데 고치니까 바로됨

bfs 정복 끝

//사담

트리 , 플로이드와샬 , 다익스트라 , 크루스칼 , DP
가 남았다..

대략 15문제정도니까.. 한 1~2주면 정복이 끝나고 이제 골2,골1만 도전할예정 'ㅅ'

끝까지 완주하기