Jungol[1661] - 미로 탈출 로봇

링크

Jungol[1661]

문제설명

• BFS

문제풀이

• BFS, q.size()로 step계산가능

문제코드 BFS

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main1661 {
    public static int[][] dir= {
            {0,1},    //동
            {0,-1},    //서
            {1,0},    //남
            {-1,0}    //북
    };

    public static void main(String[] args) throws IOException {
        int ans=0;
        System.setIn(new FileInputStream("res/jungol/1661.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int X = Integer.parseInt(st.nextToken());
        int Y = Integer.parseInt(st.nextToken());

        int[][] map = new int[Y][X];

        st = new StringTokenizer(br.readLine());
        int sx = Integer.parseInt(st.nextToken())-1;
        int sy = Integer.parseInt(st.nextToken())-1;
        int ex = Integer.parseInt(st.nextToken())-1;
        int ey = Integer.parseInt(st.nextToken())-1;

        String line;
        for (int i = 0; i < Y; i++) {
            line = br.readLine();
            for (int j = 0; j < X; j++) {
                map[i][j] = line.charAt(j)-'0';
            }
        }

        LinkedList<int[]> q = new LinkedList<>();
        q.add(new int[]{sy,sx});
        map[sy][sx]=1;
        int ny=0;
        int nx=0;
        int[] now;
        int size;
        top:
        while(!q.isEmpty()) {
            size=q.size();
            for (int s = 0; s < size; s++) {
                now = q.poll();
                for (int i = 0; i < 4; i++) {
                    ny = now[0] + dir[i][0];
                    nx = now[1] + dir[i][1];
                    if(ny>=0 && ny < Y && nx>=0 && nx < X && map[ny][nx]==0) {
                        if(ny==ey && nx==ex) break top;
                        q.add(new int[] {ny,nx});
                        map[ny][nx]=1;
                    }
                }
            }
            ans++;
        }
        ans++;
        System.out.println(ans);
    }
}

문제코드 DFS

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main1661_DFS {
    public static int[][] dir= {
            {0,1},    //동
            {0,-1},    //서
            {1,0},    //남
            {-1,0}    //북
    };
    public static int Ans=Integer.MAX_VALUE;
    public static int Temp=0;
    public static int sx;
    public static int sy;
    public static int ex;
    public static int ey;
    public static int X;
    public static int Y;
    public static int[][] map;

    public static void DFS(int[] xy) {
        Temp++;
        if(Temp>=Ans)return;
        if(xy[0]==ey && xy[1]==ex) {
            Ans = Math.min(Ans, Temp);
            return;
        }
        map[xy[0]][xy[1]]=1;    //visited
        int ny=0;
        int nx=0;
        for (int i = 0; i < 4; i++) {
            ny = xy[0] + dir[i][0];
            nx = xy[1] + dir[i][1];
            if(ny>=0 && ny < Y && nx>=0 && nx < X && map[ny][nx]==0) {
                DFS(new int[]{ny,nx});
                Temp--;
                map[ny][nx]=0;    //원상복구
            }
        }
    }
    public static void main(String[] args) throws IOException {
        int ans=0;
        System.setIn(new FileInputStream("res/jungol/1661.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        X = Integer.parseInt(st.nextToken());
        Y = Integer.parseInt(st.nextToken());

        map = new int[Y][X];

        st = new StringTokenizer(br.readLine());
        sx = Integer.parseInt(st.nextToken())-1;
        sy = Integer.parseInt(st.nextToken())-1;
        ex = Integer.parseInt(st.nextToken())-1;
        ey = Integer.parseInt(st.nextToken())-1;

        String line;
        for (int i = 0; i < Y; i++) {
            line = br.readLine();
            for (int j = 0; j < X; j++) {
                map[i][j] = line.charAt(j)-'0';
            }
        }

        DFS(new int[] {sy,sx});

        System.out.println(Ans-1);
    }
}

아쉬운점

• st = new StringTokenizer(br.readLine()," "); 에러뜸
• st = new StringTokenizer(br.readLine()); 하면 " \t\n\r\f"이라 에러가 안뜨는듯
• 100x100탐색은 DFS로 하면 부담스러움
  • 10000개의 노드 4방향
  • 가지치기 잘해야함 memoization필요

잘한점

• BFS