글 읽기 - [2206번 자바] 제 코드와 정답코드의 차이를 알려주세요

hansorly 3년 전 0

39번째 줄부터 봐주시면 감사하겠습니다.

첫번쨰 코드가 틀린 코드입니다

틀린코드(제가 작성한 코드)에서는 1. break 를 사용했던 point 가 왔을 떄 2. break를 사용하지 않았던 point 가 왔을때

두가지 경우로 나누어 풀려고 했고

정답코드에서는 break 사용유무를 큐에 넣기 직전 고려했습니다. (구글링해서 참고함)

제가 오늘 하루종일 생각하기엔 break 를 썻는지 안썻는지에 대해 먼저 고려했는지 vs 나중에 고려했는지

차이 밖에 없어보입니다 . (if문 갯수 차이도 있음)

제 코드(틀린코드)는 3%~7% 구간에서 시간초과가 발생합니다 .

시간초과가 발생하는 논리적인 이유가 있어보이는데 도저히 모르겠습니다 . 도와주십시오 .

import java.util.*;
import java.io.*;

public class Main {
    static int n;
    static int m;
    static int arr[][];
    static boolean check[][][];
    static int a[][]={
        {-1,0},{1,0},{0,1},{0,-1}
    };
    public static void main(String[] args) throws IOException {
        // Scanner scanner = new Scanner(System.in);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 
        String s[] = br.readLine().split(" ");
        n= Integer.parseInt(s[0]); m= Integer.parseInt(s[1]);
        arr = new int[n+1][m+1];
        check = new boolean[2][n+1][m+1];
        for(int i=0;i<2;i++){
            for(int j=0;j<n;j++){
                Arrays.fill(check[i][j],false);
            }
        }
        boolean flag=false;
        Queue<point> queue = new LinkedList();
        
        for(int i=0;i<n;i++){
            s=br.readLine().split("");
            for(int j=0;j<m;j++){
                arr[i][j]=Integer.parseInt(s[j]);
            }
    } 
        queue.add(new point(0,0,0,false));
        check[0][0][0]=true;
        check[1][0][0]=true;
        
        
        while(!queue.isEmpty()){
            point temp = queue.poll();
            int row = temp.row;
            int col = temp.col;
            int cnt = temp.cnt;
            boolean had= temp.had;
            int visit=0;
            if(had)visit=1;

            //check[visit][row][col]=true;//방문표시

            if(row==n-1&&col==m-1){//종료지점
                System.out.println(cnt+1);
                flag= true;
                break;
            }

            int temp_row;
            int temp_col;

            /*-------------틀린코드---------------
            
            if(had==false){//break를 사용하지 않았을때
                
                for(int i=0;i<4;i++){
                    temp_row=a[i][0]+row;
                    temp_col=a[i][1]+col;
                    if(temp_row<=n-1&&temp_row>=0&&temp_col<=m-1&&temp_col>=0){
                    //범위 안에 있을때
                        if(arr[temp_row][temp_col]==0){
                            //이동가능
                            if(!check[visit][temp_row][temp_col]){
                            queue.add(new point(temp_row,temp_col,cnt+1,had));
                            check[visit][row][col]=true;//방문표시
                            }
                        }
                        else if(arr[temp_row][temp_col]==1){
                            if(!check[1][temp_row][temp_col]){
                            queue.add(new point(temp_row,temp_col,cnt+1,true));
                            check[1][row][col]=true;//방문표시
                            }
                        }
                    }
                }                

            }else{//break 사용
                for(int i=0;i<4;i++){
                    temp_row=a[i][0]+row;
                    temp_col=a[i][1]+col;
                    if(temp_row<=n-1&&temp_row>=0&&temp_col<=m-1&&temp_col>=0){
                    //범위 안에 있을때 
                        if(arr[temp_row][temp_col]==0){
                            //이동가능
                            if(!check[visit][temp_row][temp_col]){
                            check[visit][row][col]=true;//방문표시
                            queue.add(new point(temp_row,temp_col,cnt+1,had));
                            }
                        }
                    }
                }

            }*/
            
            /*------------정답코드 ----------*/
            /*for(int i=0;i<4;i++){
                temp_row=a[i][0]+row;
                temp_col=a[i][1]+col;
                if(temp_row<=n-1&&temp_row>=0&&temp_col<=m-1&&temp_col>=0){
                    
            
                if(arr[temp_row][temp_col]==1){
                    if(visit==0&&!check[1][temp_row][temp_col]){
                        check[1][temp_row][temp_col]=true;
                        queue.add(new point(temp_row,temp_col,cnt+1,true));
                    }
                }
                else{
                    if(!check[visit][temp_row][temp_col]){
                        queue.add(new point(temp_row,temp_col,cnt+1,had));
                        check[visit][temp_row][temp_col]=true;
                    }
                }
            }
        }*/
     }//bfs 종료 
        if(!flag){
            System.out.println(-1);
        }


    }
}

class point{
    int row;
    int col;
    int cnt;
    boolean had;
    
        public point(int row,int col,int cnt,boolean had){
            this.row=row;
            this.col=col;
            this.cnt=cnt;
            this.had=had;
        }
}

hansorly 3년 전 0

다음날 바로 찾았슴니다 하핫..

갱신할때 temp row로 갱신해야하는데 row로 갱신햇습니당..

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

문제

문제

출처

ICPC

[2206번 자바] 제 코드와 정답코드의 차이를 알려주세요

hansorly 3년 전 0

hansorly 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말