글 읽기 - [Java] 정말 모르겠습니다.. 반례가 있을까요

dl0312 6년 전 1

다익스트라 알고리즘과 우선순위 큐를 이용해서 풀었습니다.

문제 테스트 케이스 질문에 올라 온 테스트 케이스는 다 통과하고 특이한 것들도 다 통과했는데 틀렸습니다 ㅠㅠ...

며칠째 고민중인데 정말 안풀리네요... 도움의 손길이 필요합니다.

반례라도 제시해주신다면 감사하겠습니다.

[ 시도해본 테스트 케이스 ]

1 1

=10

1 2

4 3

= 4

1 2

3 4

= 4

5 6
5 5 5 5 7 100
7 7 7 7 5 7
7 7 7 7 5 7
7 7 7 7 5 7
7 7 7 7 5 5

7 7
0 0 0 0 0 0 3
3 3 3 3 3 0 3
3 3 3 3 3 0 3
0 0 0 0 3 0 3
0 3 3 3 3 3 3
0 3 3 3 3 3 3
0 0 0 0 0 0 0

7 7
0 0 0 0 0 0 3
3 3 3 3 3 0 3
3 3 3 3 3 0 3
3 0 0 0 0 0 3
0 3 3 3 3 3 3
0 3 3 3 3 3 3
0 0 0 0 0 0 0

10 8
0 0 0 0 0 0 0 3
3 3 3 3 3 3 0 3
3 3 3 3 3 3 0 3
0 0 0 0 3 3 0 3
0 3 3 3 3 3 0 3
0 3 3 0 0 0 0 3
0 3 3 0 0 0 0 3
0 3 3 3 3 3 3 3
0 3 3 3 3 3 3 3
0 0 0 0 0 0 0 0

6 5

0 0 0 0 3

3 3 3 0 3

0 0 3 0 0

0 3 3 3 3

0 0 0 0 0

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

//	BOJ - 14948
//	Algorithm - ?
//	2017 Sogang Programming Contest - Champion F번

public class Main {
	static int n,m;
	static int [][] map = new int [101][101];
	static int [][] cost = new int [101][101];
	static boolean [][][] dir_cnt = new boolean [101][101][4];
	static int dx [] = { 0,1,0,-1,0,2,0,-2 };
	static int dy [] = { 1,0,-1,0,2,0,-2,0 };
	static int length;
	
	public static class PosComparator implements Comparator<Pos>
	{
	    public int compare(Pos x, Pos y)
	    {
	        if (x.cost < y.cost)
	        {
	            return -1;
	        }
	        if (x.cost > y.cost)
	        {
	            return 1;
	        }
	        return 0;
	    }
	}
	
	
	public static class Pos{
		int x,y;
		int cost;
		int dir;//0:east,1:south,2:west,4:north
		boolean item = false;
		public Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	public static void main(String[] args){
		Scanner scn = new Scanner(System.in);
		Comparator<Pos> comparator = new PosComparator();
		PriorityQueue<Pos> q = new PriorityQueue<>(comparator);
		n = scn.nextInt();
		m = scn.nextInt();
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++) {
				map[i][j] = scn.nextInt();
				cost[i][j] = -1;
				for(int k=0;k<4;k++) {
					dir_cnt[i][j][k] = false;
				}
			}
		Pos now = new Pos(0,0);
		cost[now.x][now.y] = map[now.x][now.y];
		now.cost = cost[now.x][now.y];
		q.add(now);
		while(!q.isEmpty()) {
			now = q.poll();
			for(int i=0;i<4;i++) {
				Pos tmp = new Pos(now.x+dx[i],now.y+dy[i]);
				tmp.dir=i;
				tmp.item = now.item;
				if(tmp.x>=0 && tmp.x<n && tmp.y>=0 && tmp.y<m ) {
					if(cost[tmp.x][tmp.y]==-1) {
						cost[tmp.x][tmp.y]=Math.max(cost[now.x][now.y],map[tmp.x][tmp.y]);
						tmp.cost = cost[tmp.x][tmp.y];
						if(tmp.item==false) {
							dir_cnt[tmp.x][tmp.y][i] = true;
						}
						q.add(tmp);
					}
					else if(cost[tmp.x][tmp.y] > Math.max(cost[now.x][now.y],map[tmp.x][tmp.y])) {
						cost[tmp.x][tmp.y] = Math.max(cost[now.x][now.y],map[tmp.x][tmp.y]);
						tmp.cost = cost[tmp.x][tmp.y];
						if(tmp.item==false) {
							dir_cnt[tmp.x][tmp.y][i] = true;
						}
						q.add(tmp);
					}
					else if(cost[tmp.x][tmp.y] == Math.max(cost[now.x][now.y],map[tmp.x][tmp.y])) {
						if(tmp.item==false) {
							for(Pos p:q) {
								if(p.x==tmp.x && p.y==tmp.y) {
									p.item = false;
								}
							}
							if(dir_cnt[tmp.x][tmp.y][i]==false) {
								tmp.cost = Math.max(cost[now.x][now.y],map[tmp.x][tmp.y]);
								dir_cnt[tmp.x][tmp.y][i] = true;
								q.add(tmp);
							}
						}
					}
				}
			}
			if(now.item==false) {
				int i=now.dir+4;
				Pos tmp = new Pos(now.x+dx[i],now.y+dy[i]);
				tmp.item = true;
				if(tmp.x>=0 && tmp.x<n && tmp.y>=0 && tmp.y<m ) {
					if(cost[tmp.x][tmp.y]==-1) {
						cost[tmp.x][tmp.y]=Math.max(cost[now.x][now.y],map[tmp.x][tmp.y]);
						tmp.cost = cost[tmp.x][tmp.y];
						q.add(tmp);
					}
					else if(cost[tmp.x][tmp.y] > Math.max(cost[now.x][now.y],map[tmp.x][tmp.y])) {
						cost[tmp.x][tmp.y] = Math.max(cost[now.x][now.y],map[tmp.x][tmp.y]);
						tmp.cost = cost[tmp.x][tmp.y];
						q.add(tmp);
					}
				}
			}
		}
		System.out.println(cost[n-1][m-1]);
	}
}

jh05013 6년 전 2

7 7
0 0 0 0 0 0 3
3 3 3 3 3 0 3
3 3 3 3 3 0 3
0 0 0 0 3 0 3
0 3 3 3 3 3 3
0 3 3 3 3 3 3
0 0 0 0 0 0 0

이건 0이 나와야 합니다.

dl0312 6년 전 0

답변 감사드립니다 그런데 어떻게 0이 나오는지 알 수 있을까요? ㅠㅠ

"가던 방향 그대로만 타일을 한 칸 뛰어넘을 수 있다" 는 조건이 특수장비 사용 전에 특수장비를 사용하는 방향과 같은 방향으로 갔어야한 것 같아서

제가 문제를 잘못이해한건가요

jh05013 6년 전 1

타일을 뛰어넘는 도중에 방향을 바꿀 수 없다는 뜻입니다. 오해의 소지가 있네요.

dl0312 6년 전 0

아 그런거군요...ㅠㅠ 제가 본 블로그 글에서도 마지막같은 예시들으셨는데 저랑 비슷한 오해를 했나보네요

감사합니다!!

jh05013 6년 전 0

이상하군요. 저는 "타일을 뛰어넘는 도중에 방향을 바꿀 수 없다"로 해석하고 풀어서 정답을 받았는데, "도움닫기가 필요하다"라고 해석하신 분의 코드도 정답을 받았습니다. 표현을 명확히 수정하고 데이터 추가를 해야 될 것 같습니다.

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

문제

문제

출처

ICPC

[Java] 정말 모르겠습니다.. 반례가 있을까요

dl0312 6년 전 1

jh05013 6년 전 2

dl0312 6년 전 0

jh05013 6년 전 1

dl0312 6년 전 0

jh05013 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말