글 읽기 - 왜 틀렸을까용,,,,,,??

le_effort 4년 전 0

블로그의 성공코드를 참조 해 보았는데

제가 코딩 실력이 비슷해서 그런지...

실제로는 다르겠지만 제 코드랑 다 비슷해보여요 ㅠㅠㅠㅠㅠ

어디가 잘못 된 건지 찾아주시면 감사하겠습니다 ㅠ...

import java. io.*;
import java. util.*;
public class Main {
	static int[] dx = {0,0,1,-1};
	static int[] dy = {1,-1,0,0};
	static int[][] arr;
	static boolean visited[][][];
	static int time[][];
	static int n,m;
	static int ans=Integer.MAX_VALUE;
	static boolean bl;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] t = br.readLine().split(" ");
		n = Integer.parseInt(t[0]);
		m = Integer.parseInt(t[1]);
		arr = new int[n+1][m+1];
		visited = new boolean[n+1][m+1][2];
		time = new int[n+1][m+1];
		for(int i=1; i<=n; i++) {
			String[] input = br.readLine().split("");
			for(int j=1; j<=m ; j++) {
				arr[i][j]=Integer.parseInt(input[j-1]);
			}
		}
		bfs();
		if(bl) {
			System.out.println(time[n][m]+1);
		}
		else {
			System.out.println(-1);
		}
		
	}
	public static void bfs() {
		Queue<Node> q = new LinkedList<>();
		visited[1][1][0] = true;
		visited[1][1][1] = true;
		q.add(new Node(1,1,0));
		while(!q.isEmpty()) {
			Node a = q.poll();
			if(a.x ==n && a.y ==m) {
				bl = true;
			}
			for(int i=0; i<4; i++) {
				int x_1 = a.x+dx[i];
				int y_1 = a.y+dy[i];
				if(x_1>=1 && y_1>=1 && x_1<=n && y_1<=m) {
					
					if(arr[x_1][y_1]==1 && a.drill==0) {
						if(!visited[x_1][y_1][1]) {
							time[x_1][y_1] = time[a.x][a.y]+1;
							visited[x_1][y_1][1] = true;
							q.add(new Node(x_1,y_1,1));
						}
					}
					// n 이랑 m 위치 관계 잘 보깉ㄴㅋ
					else if(arr[x_1][y_1]==0){
								if(!visited[x_1][y_1][a.drill]) {
								visited[x_1][y_1][a.drill] = true;
								time[x_1][y_1] = time[a.x][a.y]+1;
								q.add(new Node(x_1,y_1,a.drill));
						}
					}
				}
			}
		}
	}
}
class Node{
	int x;
	int y;
	int drill;
	Node(int x, int y, int drill){
		this.x= x;
		this. y= y;
		this.drill = drill;
	}
}

akaishuichi 4년 전 1

반례 제시해드립니다.

6 4

0000

1110

0110

0000

0111

0000

이 예제를 돌렸을 때 정답은 9지만 15가 나옵니다.

도착점에 도착한 순간 무조건 최단거리로 간 것인데 님의 코드는 멈추지 않고 다른 경로로 돌아가는 경우가 time[n][m]에 체크가 됩니다.

if(a.x ==n && a.y ==m) { bl = true; break; }

이 부분에만 break를 걸어주면 AC를 받습니다.

le_effort 4년 전 0

아 이해 됐습니다 감사합니다 !!!

정말 혼자 골머리 앓고 있었는데 정말 감사합니다 ㅠㅠ

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

문제

문제

출처

ICPC

왜 틀렸을까용,,,,,,??

le_effort 4년 전 0

akaishuichi 4년 전 1

le_effort 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말