글 읽기 - 게시판의 모든 테스트 케이스는 다 맞는데 7%에서 실패합니다..

laugh4mile 2년 전 0

몇번을 다시 풀어도 모르겠습니다..

게시판에서 보이는 실수들 중

1. 목적지가 같을경우

2. 앞사람의 도착점이 뒷사람의 출발점일 경우

3. 승객 선택 우선순위 정하기

4. 승객이 도착지로 갈 수 없는 경우 (벽에 막혀서)

의 상황을 모두 처리했다고 생각했는데 안됩니다..

무엇이 잘못된 걸까요?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N,M,fuel, passanger[][], taxiR,taxiC,cur,plus;
	static boolean isVisited[][];
	static List<Node> dest = new ArrayList<>();
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		//input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		fuel = Integer.parseInt(tokens.nextToken());
		passanger = new int[N][N];
		isVisited = new boolean[N][N];
		for(int r=0; r<N; r++) {
			tokens = new StringTokenizer(input.readLine());
			for(int c=0; c<N; c++) {
				int map = Integer.parseInt(tokens.nextToken());
				passanger[r][c] = map;
			}	
		}
		tokens = new StringTokenizer(input.readLine());
		taxiR = Integer.parseInt(tokens.nextToken())-1;
		taxiC = Integer.parseInt(tokens.nextToken())-1;
		int cnt = 2;
		for(int m=0; m<M; m++) {
			tokens = new StringTokenizer(input.readLine());
			int pr = Integer.parseInt(tokens.nextToken())-1;
			int pc = Integer.parseInt(tokens.nextToken())-1;
			int dr = Integer.parseInt(tokens.nextToken())-1;
			int dc = Integer.parseInt(tokens.nextToken())-1;
			passanger[pr][pc] = cnt; 
			dest.add(new Node(dr, dc, cnt++));
		} // 입력 끝

		boolean isFailed = false;
		
		for(int m=0; m<M; m++) {
			findPass(); // 가장 가까운 승객 찾기
			if(fuel<=0) {
				isFailed = true;
				break;
			}
			passanger[taxiR][taxiC] = 0; // 해당 승객은 이제 제외함.
			
			findDest(cur); // cur = 승객 번호이자 도착번호
			if(fuel<0) { // 0은 봐줌
                isFailed = true;
                break; 
            }
			fuel += plus;
			plus = 0;
		}
		
		for(int r=0; r<N; r++) {
			for(int c=0; c<N; c++) {
				if(passanger[r][c] > 1) { // 승객이 남은 경우 실패이다.
					isFailed = true;
					break;
				}
			}	
		}
		
		if(isFailed || dest.size() > 0) { // 목적지가 남아도 실패이다.
			System.out.println(-1);
		}else {
			System.out.println(fuel);
		}
	}
	
	private static void findPass() { // 가까운 승객 찾기
		for(int r=0; r<N; r++) {
			for(int c=0; c<N; c++) {
				isVisited[r][c] = false;
			}	
		}
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(taxiR, taxiC, 0));
		isVisited[taxiR][taxiC] = true;
		
		while(!queue.isEmpty()) {
			Node front = queue.poll();
			
			if(passanger[front.r][front.c] > 1) { // 만약 승객을 발견하면
				taxiR = front.r; // 택시 위치 초기화
				taxiC = front.c; 
				fuel -= front.d; // 연료 감소
				cur = passanger[front.r][front.c];
				break;
			}
			for(int d=0; d<4; d++) {
				int nr = front.r + dr[d];
				int nc = front.c + dc[d];
				if(isIn(nr, nc) && !isVisited[nr][nc] && passanger[nr][nc] != 1) {
					isVisited[nr][nc] = true;
					queue.offer(new Node(nr, nc, front.d+1));
				}
			}
		}
	}
	
	private static void findDest(int cur) { // cur 승객의 목적지 찾기
		for(int r=0; r<N; r++) {
			for(int c=0; c<N; c++) {
				isVisited[r][c] = false;
			}	
		}
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(taxiR, taxiC, 0));
		isVisited[taxiR][taxiC] = true;
		
		outer : while(!queue.isEmpty()) {
			Node front = queue.poll();
			for(int i=0; i<dest.size(); i++) {
				if(front.r == dest.get(i).r && front.c == dest.get(i).c && dest.get(i).d == cur) {
					taxiR = front.r;
					taxiC = front.c;
					fuel -= front.d;
					plus = front.d * 2;
					dest.remove(i); // 해당 목적지는 삭제.
					break outer;
				}
			}
			for(int d=0; d<4; d++) {
				int nr = front.r + dr[d];
				int nc = front.c + dc[d];
				if(isIn(nr, nc) && !isVisited[nr][nc] && passanger[nr][nc] != 1) {
					isVisited[nr][nc] = true;
					queue.offer(new Node(nr, nc, front.d+1));
				}
			}
		}
		
	}
	
	
	static boolean isIn(int r, int c) {
		return(r>=0 && c>=0 && r<N && c<N);
	}
	static int dr[] = {-1,0,0,1}; // 상,좌,우,하 <- 순서 중요
	static int dc[] = {0,-1,1,0};
	static class Node{
		int r;
		int c;
		int d;
		public Node(int r, int c, int d) {
			super();
			this.r = r;
			this.c = c;
			this.d = d;
		}
	}
	static String src =
			"2 1 1\r\n" + 
			"0 0\r\n" + 
			"0 0\r\n" + 
			"2 2\r\n" + 
			"2 2 2 1"; 
}

laugh4mile 2년 전 0

승객 선택을 잘못했네요 ㅜㅜ

ngeol564 2년 전 0

혹시 어떻게 수정하셨나요?

laugh4mile 2년 전 2

ngeol564

오래되서 기억이 잘 안나는데 최종 제출해서 통과한 코드입니다!

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

public class Main {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N,M,fuel, passanger[][], taxiR,taxiC,cur,plus;
	static boolean isVisited[][];
	static List<Node> dest = new ArrayList<>();
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		//input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		fuel = Integer.parseInt(tokens.nextToken());
		passanger = new int[N][N];
		isVisited = new boolean[N][N];
		for(int r=0; r<N; r++) {
			tokens = new StringTokenizer(input.readLine());
			for(int c=0; c<N; c++) {
				int map = Integer.parseInt(tokens.nextToken());
				passanger[r][c] = map;
			}	
		}
		tokens = new StringTokenizer(input.readLine());
		taxiR = Integer.parseInt(tokens.nextToken())-1;
		taxiC = Integer.parseInt(tokens.nextToken())-1;
		int cnt = 2;
		for(int m=0; m<M; m++) {
			tokens = new StringTokenizer(input.readLine());
			int pr = Integer.parseInt(tokens.nextToken())-1;
			int pc = Integer.parseInt(tokens.nextToken())-1;
			int dr = Integer.parseInt(tokens.nextToken())-1;
			int dc = Integer.parseInt(tokens.nextToken())-1;
			passanger[pr][pc] = cnt; 
			dest.add(new Node(dr, dc, cnt++));
		} // 입력 끝

		boolean isFailed = false;
		for(int m=0; m<M; m++) {
			findPass(); // 가장 가까운 승객 찾기
			if(fuel<=0) {
				isFailed = true;
				break;
			}
			passanger[taxiR][taxiC] = 0; // 해당 승객은 이제 제외함.
			
			findDest(cur); // cur = 승객 번호이자 도착번호
			if(fuel<0) { // 0은 봐줌
				isFailed = true;
				break; 
			}
			fuel += plus;
			plus = 0;
		}
		
		for(int r=0; r<N; r++) {
			for(int c=0; c<N; c++) {
				if(passanger[r][c] > 1) { // 승객이 남은 경우 실패이다.
					isFailed = true;
					break;
				}
			}	
		}
		if(isFailed || dest.size() > 0) { // 목적지가 남아도 실패이다.
			System.out.println(-1);
		}else {
			System.out.println(fuel);
		}
	}
	
	private static void findPass() { // 가까운 승객 찾기
		for(int r=0; r<N; r++) {
			for(int c=0; c<N; c++) {
				isVisited[r][c] = false;
			}	
		}
		PriorityQueue<Node> queue = new PriorityQueue<>();
//		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(taxiR, taxiC, 0));
		isVisited[taxiR][taxiC] = true;
		
		while(!queue.isEmpty()) {
			Node front = queue.poll();
			
			if(passanger[front.r][front.c] > 1) { // 만약 승객을 발견하면
				taxiR = front.r; // 택시 위치 초기화
				taxiC = front.c; 
				fuel -= front.d; // 연료 감소
				cur = passanger[front.r][front.c];
				break;
			}
			for(int d=0; d<4; d++) {
				int nr = front.r + dr[d];
				int nc = front.c + dc[d];
				if(isIn(nr, nc) && !isVisited[nr][nc] && passanger[nr][nc] != 1) {
					isVisited[nr][nc] = true;
					queue.offer(new Node(nr, nc, front.d+1));
				}
			}
		}
	}
	
	private static void findDest(int cur) { // cur 승객의 목적지 찾기
		for(int r=0; r<N; r++) {
			for(int c=0; c<N; c++) {
				isVisited[r][c] = false;
			}	
		}
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(taxiR, taxiC, 0));
		isVisited[taxiR][taxiC] = true;
		
		outer : while(!queue.isEmpty()) {
			Node front = queue.poll();
			for(int i=0; i<dest.size(); i++) {
				if(front.r == dest.get(i).r && front.c == dest.get(i).c && dest.get(i).d == cur) {
					taxiR = front.r;
					taxiC = front.c;
					fuel -= front.d;
					plus = front.d * 2;
					dest.remove(i); // 해당 목적지는 삭제.
					break outer;
				}
			}
			for(int d=0; d<4; d++) {
				int nr = front.r + dr[d];
				int nc = front.c + dc[d];
				if(isIn(nr, nc) && !isVisited[nr][nc] && passanger[nr][nc] != 1) {
					isVisited[nr][nc] = true;
					queue.offer(new Node(nr, nc, front.d+1));
				}
			}
		}
		
	}
	
	
	static boolean isIn(int r, int c) {
		return(r>=0 && c>=0 && r<N && c<N);
	}
	static int dr[] = {-1,0,0,1}; // 상,좌,우,하 <- 순서 중요
	static int dc[] = {0,-1,1,0};
	static class Node implements Comparable<Node>{
		int r;
		int c;
		int d;
		public Node(int r, int c, int d) {
			super();
			this.r = r;
			this.c = c;
			this.d = d;
		}
		@Override
		public int compareTo(Node o) {
			if(this.d == o.d) {
				if(this.r == o.r) {
					return Integer.compare(this.c, o.c);
				}
				return Integer.compare(this.r, o.r);
			}
			return Integer.compare(this.d, o.d);
		}
	}
	static String src =
			"6 3 2\r\n" + 
			"0 0 1 0 0 0\r\n" + 
			"0 0 1 0 0 0\r\n" + 
			"0 0 0 1 0 0\r\n" + 
			"0 0 0 1 0 0\r\n" + 
			"0 0 0 0 1 0\r\n" + 
			"0 0 0 1 0 0\r\n" + 
			"1 1\r\n" + 
			"1 1 1 2\r\n" + 
			"1 2 2 2\r\n" + 
			"2 2 2 3"; 
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

게시판의 모든 테스트 케이스는 다 맞는데 7%에서 실패합니다..

laugh4mile 2년 전 0

laugh4mile 2년 전 0

ngeol564 2년 전 0

laugh4mile 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말