developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • BOJ파이썬풀이
  • ARIMA모형
  • 삼성코테자바준비
  • MA모형
  • 카카오코테
  • 삼성코테파이썬
  • 데이터분석
  • 삼성코테구현문제추천
  • 통계학
  • 삼성코테기출자바풀이
  • SW역량테스트파이썬풀이
  • 삼성코테자바꿀팁
  • 백준파이썬풀이
  • 시계열분석
  • 카카오코테java풀이
  • 삼성코테파이썬준비
  • 삼성코테구현풀이
  • 운영체제인터럽트
  • 통계분석
  • c++디자인패턴
  • 삼성코테기출
  • 삼성코테자바풀이
  • AR모형
  • 삼성코테준비
  • 시계열
  • c++ 빌더 패턴
  • SW역량테스트파이썬
  • Arima
  • 코테파이썬
  • 삼성코테파이썬풀이

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

BOJ - 스타트택시 19238번 (JAVA)

2022. 4. 30. 13:41

❓ 문제 - 백준 스타트택시 19238번 - JAVA 풀이법

 

출처 

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

 

19238번: 스타트 택시

첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다

www.acmicpc.net

 

 

 

📝 문제해결법

1. 이 문제는 BFS+구현으로 풀었다.

  • 2차원배열 map으로 활동할 영역에 대한 정보를 관리한다.
  • cus_map으로 손님의 출발지의 위치를 저장하고, cus로 손님의 출발지 x, y 도착치 x,y를 저장해서 관리한다.
  • 택시는 모든 손님을 다 태울 때나 운행이 종료될까지 운행 되는데 bfs1()함수를 통해 현재 택시의 위치에서 손님들까지의 거리를 계산하고 거리의 최소, 거리가 같으면 행의 최소, 행이 같으면 열의 최소의 조건으로 정렬한다. 따라서 정렬 조건에 맞춰 태울 손님을 한 명 고른다. 여기서 주의할 점은 남은 손님들 중에 벽 때문에 갈 수 없는 손님이 있으면 운행을 강제 종료한다.
  • 정렬 조건에 맞춰 태울 손님을 한 명 고르고 해당 손님의 목적지까지의 최단거리를 bfs2()를 통해 구한다. 이때도 손님의 도착지가 갈 수 없는 곳이라면 -1을 출력하고 운행을 종료한다. 
  • 손님의 출발지로 갈 수 있고, 해당 출발지에서 목적지까지 갈 수 있으면 두 거리의 합을 현재 남은 오일이랑 비교해서 남은 오일양으로 갈 수 없다면 운행을 종료한다. 

 

 

💻 소스코드

// BOJ - 스타트 택시(19238번)
// BFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_19238 {
	public static int n, m, oil, people;
	public static int[][] map;
	public static int[][] cus_map;
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};
	public static boolean[] check;
	public static int t_x, t_y;
	public static class Node implements Comparable<Node>{
		int x;
		int y;
		int dis;
		public Node(int x, int y, int dis) {
			this.x = x;
			this.y = y;
			this.dis = dis;
		}
		@Override
		public int compareTo(Node o) {
			if(this.dis == o.dis) {
				if(this.x == o.x) {
					return this.y - o.y;
				} 
				return this.x - o.x;
			}
			return this.dis - o.dis;
		}
	}
	public static int[][] cus;

	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());
		m = Integer.parseInt(st.nextToken());
		oil = Integer.parseInt(st.nextToken());
		map = new int[n][n];
		cus = new int[m+1][4];
		cus_map = new int[n][n];
		check = new boolean[m+1];
		
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0;j<n;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		
		st = new StringTokenizer(br.readLine(), " ");
		t_x = Integer.parseInt(st.nextToken())-1;
		t_y = Integer.parseInt(st.nextToken())-1;
		
		for(int i=1;i<=m;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0;j<4;j++) {
				int num = Integer.parseInt(st.nextToken())-1;
				cus[i][j] = num;
			}
			cus_map[cus[i][0]][cus[i][1]] = i;
		}
		
		people = m;
		boolean end = false;
		while (true) {
			if(people == 0) {
				break;
			}
			
			// 손님 고르기
			Node node = bfs1();
			if(node == null) {
				end = true;
				break;
			}
			int cus_num = cus_map[node.x][node.y];
			// 손님 데려다 주기
			
			int cal1 = node.dis;
			int cal2 = bfs2(node.x, node.y, cus[cus_num][2], cus[cus_num][3]);
	
			
			if(oil < cal1+cal2 || cal2 == -1) {
				end = true;
				break;
			}
			
			oil -= (cal1+cal2);
			oil += (cal2 * 2);
			check[cus_num] = true;
			cus_map[node.x][node.y] = 0;
			t_x = cus[cus_num][2];
			t_y = cus[cus_num][3];
			people--;
				
		}
		if(end) System.out.println(-1);
		else System.out.println(oil);
	}
	
	public static Node bfs1() {
		boolean[][] visited = new boolean[n][n];
		Queue<Node> q = new LinkedList<>();
		PriorityQueue<Node> pq = new PriorityQueue<>();
		visited[t_x][t_y] = true;
		q.offer(new Node(t_x, t_y, 0));
		while(!q.isEmpty()) {
			Node node = q.poll();
			if(cus_map[node.x][node.y] >= 1 && !check[cus_map[node.x][node.y]]) {
				pq.add(new Node(node.x, node.y, node.dis));
			}
			for(int d=0;d<4;d++) {
				int nx = node.x + dx[d];
				int ny = node.y + dy[d];
				
				if(0 <= nx && nx < n && 0 <= ny && ny < n) {
					if(!visited[nx][ny] && map[nx][ny] != 1) {
						visited[nx][ny] = true;
						q.add(new Node(nx, ny, node.dis+1));
					}
				}
			}
		}
		if(pq.isEmpty()) return null;
		return pq.poll();
		
	}
	
	public static int bfs2(int s_x, int s_y, int e_x, int e_y) {
		boolean[][] visited = new boolean[n][n];
		Queue<Node> q = new LinkedList<>();

		visited[s_x][s_y] = true;
		q.offer(new Node(s_x, s_y, 0));
		int dis = -1;
		while(!q.isEmpty()) {
			Node node = q.poll();
			if(node.x == e_x && node.y == e_y) {
				return node.dis;
			}
			for(int d=0;d<4;d++) {
				int nx = node.x + dx[d];
				int ny = node.y + dy[d];
				if(0 <= nx && nx < n && 0 <= ny && ny < n) {
					if(!visited[nx][ny] && map[nx][ny] != 1) {
						visited[nx][ny] = true;
						q.add(new Node(nx, ny, node.dis+1));
					}
				}
			}
		}
		return dis;
	}

}

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - 마법사 상어와 파이어볼 20056번 (JAVA)  (0) 2022.04.30
BOJ - 컨베이어 벨트 위의 로봇 20055번 (JAVA)  (0) 2022.04.30
BOJ - 어른 상어 19237번 (JAVA)  (0) 2022.04.30
BOJ - 청소년 상어 19236번 (JAVA)  (0) 2022.04.30
BOJ - 모노미노도미노2 20061번 (JAVA)  (0) 2022.04.30
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - 마법사 상어와 파이어볼 20056번 (JAVA)
    • BOJ - 컨베이어 벨트 위의 로봇 20055번 (JAVA)
    • BOJ - 어른 상어 19237번 (JAVA)
    • BOJ - 청소년 상어 19236번 (JAVA)
    developer-ellen
    developer-ellen

    티스토리툴바