글 읽기 - 어디가 틀린건가요? 잘모르겟씁니다..

baepoce 4년 전 0

제가한게 다익스트라가 맞는건가요?

일단 문제가 틀려서 잘 모르겠습니다 고수님들 부탁드립니다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class XY{
    int x,y;
    XY(int x, int y){
        this.x=x;
        this.y=y;
    }
}
public class test4485 {
	static int[] dx= {-1,0,1,0};
	static int[] dy= {0,1,0,-1};
	static int[][] map;
	static int[][] ans;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int cnt=1;
		int t=Integer.parseInt(br.readLine());
		while(t!=0) {
			map=new int[t+1][t+1];
			ans=new int[t+1][t+1];
			for(int i=1; i<=t; i++) {
				st=new StringTokenizer(br.readLine());
				for(int j=1; j<=t; j++) {
					map[i][j]=Integer.parseInt(st.nextToken());
				}
			}
			ans[1][1]=map[1][1];
			Queue<XY> q=new LinkedList<>();
			q.add(new XY(1,1));
			while(!q.isEmpty()) {
				XY xy=q.poll();
				for(int i=0; i<4; i++) {
					int nx=xy.x+dx[i];
					int ny=xy.y+dy[i];
					if(nx<1 || ny<1 || nx>t || ny>t) 
						continue;
					if(ans[nx][ny]!=0) {
						if(ans[nx][ny]>ans[xy.x][xy.y]+map[nx][ny]) {
							ans[nx][ny]=ans[xy.x][xy.y]+map[nx][ny];
							q.add(new XY(nx,ny));
						}
					}
					else if(ans[nx][ny]==0) {
						ans[nx][ny]=map[nx][ny]+ans[xy.x][xy.y];
						q.add(new XY(nx,ny));
					}
				}
			}
			System.out.println("Problem "+(cnt++)+": "+ans[t][t]);
			t=Integer.parseInt(br.readLine());
		}


	}

}

baepoce 4년 전 0

43~52번째줄을 고쳤더니

처음에 ans배열을 맥스벨류로 채워놓고 최소값일때 큐에집어넣는방식으로하니 맞았습니다

근데 제가 저렇게 쓴거랑 코드의 차이점이 뭔가요?

baepoce 4년 전 0

문제에 비용이0도있었군요

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

문제

문제

출처

ICPC

어디가 틀린건가요? 잘모르겟씁니다..

baepoce 4년 전 0

baepoce 4년 전 0

baepoce 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말