글 읽기 - visit 배열 체크를 하면 틀렸습니다가 나옵니다 ㅠㅠ 이유를 모르겠습니다.

ujungg25 3년 전 0

bfs를 사용해서 문제를 풀었습니다. 시간 단축을 위해 4차원 visit배열을 통해 방문체크를 했습니다.

방문체크를 하게 되면 3%에서 틀렸습니다가 나오는데 이유를 모르겠습니다..

visit 배열을 삭제하면 정상적으로 맞았습니다가 나옵니다!

왜 이런걸까요? ㅠ^ㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	
	public static int N, M;
	public static char[][] arr;
	public static LinkedList<Pair> list = new LinkedList<>();
	public static int[][][][] visit ; // 방문체크를 위해 
	public static int tot =0;
	public static class Pair{
		int x1; int y1;
		int x2; int y2; int time;
		Pair(int x1, int y1,int x2, int y2, int time){
			this.x1=x1;
			this.y1=y1;
			this.x2=x2;
			this.y2=y2;
			this.time = time;
		}
	}

	public static void solve(){
		int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
		while(!list.isEmpty()){
			Pair temp = list.remove();
			int X1 = temp.x1;
			int Y1 = temp.y1;
			int X2 = temp.x2;
			int Y2 = temp.y2;
			int time = temp.time;
			if(time >= 10) {
				tot = -1;
				return;
			}
			for(int d=0;d<4;d++){
				int x1 = X1 + dir[d][0];
				int y1 = Y1 + dir[d][1];
				int x2 = X2 + dir[d][0];
				int y2 = Y2 + dir[d][1];
				
				if((x1<0 || y1<0 || x1 >=N || y1>=M ) && (x2<0 || y2<0 || x2 >=N || y2>=M )){
					continue;
				} //두개다 범위 넘어가면 안됨
				else if (((x1<0 || y1<0 || x1 >=N || y1>=M ) && (x2 >=0 && y2>=0 && x2 <N && y2<M))
						|| ((x2<0 || y2<0 || x2 >=N || y2>=M )  && (x1 >=0 && y1>=0 && x1 <N && y1< M))){
					tot = time+1;
					return;
				} //한개가 범위가 넘어가면 끝남
				
				if(arr[x1][y1] == '#' ){ //벽을 만났을때는 원래 좌표대로 다시 설정
					x1 = X1; y1 = Y1;
				}
				if(arr[x2][y2] == '#'){ //벽을 만났을때는 원래 좌표대로 다시 설정
					x2 = X2; y2 = Y2;
				}
				//if(visit[x1][y1][x2][y2] == 0){ // 이 코드를 삭제하면 맞았습니다가 뜸. 
				//	visit[x1][y1][x2][y2] = 1;
					list.add(new Pair(x1,y1,x2,y2,time+1));
				//}
				
			}
			
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
	
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		arr = new char[N][M];
		visit = new int[N][M][N][M];
		int x1=-1; int y1=-1;
		int x2=-1; int y2=-1;
		for(int i=0;i<N;i++){
			String str = br.readLine();
			for(int j=0;j<M;j++){
				arr[i][j] = str.charAt(j);
				if(arr[i][j] == 'o' && x1==-1 && y1==-1){
					x1 =i; y1= j;
					arr[x1][y1] = '.';
				}else if(arr[i][j] == 'o' && x1!=-1 && y1!=-1){
					x2 =i; y2= j;
					arr[x2][y2] = '.';
				}
			}
		}
		
		list.add(new Pair(x1,y1,x2,y2,0));
		visit[x1][y1][x2][y2] = 1;
		solve();
		System.out.println(tot);
	}
}

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

문제

문제

출처

ICPC

visit 배열 체크를 하면 틀렸습니다가 나옵니다 ㅠㅠ 이유를 모르겠습니다.

ujungg25 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말