[백준 15558] 점프게임 -JAVA //le_effort//

숨바꼭질 문제와 비슷한 유형이다

 

아마 bfs의 기본 개념이 있다면 쉽게 풀릴 거라 생각 하지만 나도 그렇고 사람들이 가장 자주 틀리는 것이 

n초가 지나면 n번째 칸이 사라진다는 개념 일 것이다.

 

내가 첫 오답을 받았을 경우

한 칸 앞, 한칸 뒤, 반대 줄 점프 

이 3개의 과정을 하고 나서

 

bfs 진행 중 큐에서 빠질 때 time을 증가시켜줬는데 오답 코드를 첨부하겠다.

 

이 코드에서  6번째 줄과 49,50 번째 줄 만 보길 바란다.

 

    public static void bfs() {
        int time =-1;
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0,0));
        while(!q.isEmpty()) {
            time++;
            Node a= q.poll();
            
            int nx,ny;
            for(int i=0; i<=2; i++) {
                if(i==2) {
                    if(a.x==0) {
                        nx=1;
                        ny = a.y+k;
                        if(ny>=n) {
                            System.out.println(1);
                            System.exit(0);
                        }
                        if(!visited[nx][ny] && map[nx][ny]!=0) {
                            visited[nx][ny]=true;
                            q.add(new Node(nx,ny));
                        }
                    }
                    else {
                        nx =0;
                        ny = a.y+k;
                        if(ny>=n) {
                            System.out.println(1);
                            System.exit(0);
                        }
                        if(!visited[nx][ny] && map[nx][ny]!=0) {
                            visited[nx][ny]=true;
                            q.add(new Node(nx,ny));
                        }
                    }
                }
                else {
                    ny = a.y+dx[i];
                    if(ny>=n) {
                        System.out.println(1);
                        System.exit(0);
                    }
                    if(ny>=0 && !visited[a.x][ny] && map[a.x][ny]!=0) {
                        visited[a.x][ny]=true;
                        q.add(new Node(a.x,ny));
                    }
                }
            }
            map[0][time]=0;
            map[1][time]=0;
        }
        System.out.println(0);
    }

n초가 지난 후에 n번째 땅을 없앤 다고 했으니 

map이 0 인 경우는 방문을 못하니 0으로 처리하면 된다고 생각했는데 여기엔 오답이 있다

 

처음에 시간이 0일 땐 문제가 없다

시간 0 일 때 앞으로 이동   

시간 0 일 땐 뒤로 이동    

시간 0 일땐 반대 칸으로 이동  

 

이 3가지 움직임을 다 하고 난 후 조건에 맞다면 큐에 넣어준다.

 

그 후 0번째 칸이 삭제되고 

다음 큐가 poll 되는데

 

여기서부터 문제가 생긴다

큐에서 제일 먼저 들어간 시간 0 일 때 앞으로 이동한 것이 나온다(조건에 맞아 큐에 넣었다 가정)

시간이 0에서 1로 증가된다.

그럼 시간이 1일 때 앞으로 이동, 뒤로 이동, 반대 칸으로 이동하고

조건에 맞다면 큐에 넣어주고

1번째 칸을 다 삭제하고

 

이제 다음 큐를 빼고 시간이 1에서 2로 증가한다.

다음 큐에 시간이 0일 때 반대 칸으로 이동한 것이 들어있다 생각해보자

 

아직 시간이 0 일 때의 조건들이 남아있는데 시간은 2로 늘어 나 있어서 정확한 값이 나오지 않게 된다.

이를 방지하기 위해 나는 큐에 지금 큐에서 빼는 것의 시간을 따로 기록해둬 해결했다.

 

맵을 지우지 않고 ny가 time보다 크면 그 조건이 들어갈 수 있다.

 

참고로 코드에서 등장하는 if(ny > a.time 이하 생략)

이 코드에서 

ny>=a.time 이면 안되나 고민을 했었는데 

생각을 해 보면 ny에 a.time이 들어가면 어차피 그 칸은 이동한 후에 없어질 칸이라 ny> a.time이 되어야 한다.

import java.io.*;
import java.util.*;
public class Main {
    static int n,k;
    static int map[][];
    static boolean visited[][];
    static int dx[] = {1,-1};
    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]);
        k = Integer.parseInt(t[1]);
        
        visited = new boolean[2][n];
        map = new int[2][n];
        String str;
        str = br.readLine();
        
        for(int i=0; i<n; i++) {
            map[0][i] =str.charAt(i)-'0';
        }
        str = br.readLine();
        
        for(int i=0; i<n; i++) {
            map[1][i] =str.charAt(i)-'0';
        }
        bfs();
    }
    public static void bfs() {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0,0,0));
        while(!q.isEmpty()) {
            Node a= q.poll();
            int nx,ny;
            for(int i=0; i<=2; i++) {
                if(i==2) {
                    if(a.x==0) {
                        nx=1;
                        ny = a.y+k;
                        if(ny>=n) {
                            System.out.println(1);
                            System.exit(0);
                        }
                        if(ny>a.time && !visited[nx][ny] && map[nx][ny]!=0) {
                            visited[nx][ny]=true;
                            q.add(new Node(nx,ny,a.time+1));
                        }
                    }
                    else {
                        nx =0;
                        ny = a.y+k;
                        if(ny>=n) {
                            System.out.println(1);
                            System.exit(0);
                        }
                        if(ny>a.time && !visited[nx][ny] && map[nx][ny]!=0) {
                            visited[nx][ny]=true;
                            q.add(new Node(nx,ny,a.time+1));
                        }
                    }
                }
                else {
                    ny = a.y+dx[i];
                    if(ny>=n) {
                        System.out.println(1);
                        System.exit(0);
                    }
                    if(ny>a.time && !visited[a.x][ny] && map[a.x][ny]!=0) {
                        visited[a.x][ny]=true;
                        q.add(new Node(a.x,ny,a.time+1));
                    }
                }
            }
        }
        System.out.println(0);
    }
}
class Node{
    int x,y,time;
    Node(int x ,int y, int  time){
        this.x=x;
        this.y=y;
        this.time =time;
    }
}