글 읽기 - stack으로 구현한 dfs알고리즘 좀 봐주세요 ㅠㅠ

cakimmy24 6년 전 0

처음공부하는거라 ㅠㅠ 어디가 틀렷나요 ㅠㅠ

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Scanner;
 
public class Maze_dfs {
 
    public static void push(ArrayList<Integer> stack, int num){
         
        stack.add(num);
         
    }
     
    public static void pop(ArrayList<Integer> stack){
         
        stack.remove(stack.size() - 1);
         
    }
     
    public static int top(ArrayList<Integer> stack){
         
        return stack.get(stack.size() - 1);
         
    }
     
    public static boolean empty(ArrayList<Integer> stack){
         
        if(stack.isEmpty()) return true;
        else return false;
         
    }
     
    public static void DFS(int N, int M, int [][]maze, int [][]visit){
         
        ArrayList<Integer> stack = new ArrayList<Integer>();
         
        int dir[][] = {{1,0}, {0,-1}, {-1,0}, {0,1}};
         
        push(stack, 1);
        push(stack, 1);
        visit[1][1] = 1;
         
        while(!empty(stack)){
         
            int curX = top(stack);
            int curY = top(stack);
             
             
            if(curX == N && curY == M){
                System.out.println(visit[curX][curY]);
                return ;
            }
             
            for(int i = 0; i < 4; i ++){
                int tempX = curX + dir[i][0];
                int tempY = curY + dir[i][1];
                 
                if(tempX >= 1 && tempX <= N && tempY >= 1 && tempY <= M
                        && maze[tempX][tempY] == 1 && visit[tempX][tempY] == 0){ // 갈 데가 있으면
                        push(stack, tempX);
                        push(stack, tempY);
                        visit[tempX][tempY] = visit[curX][curY] + 1;
                        break;
                }
                     
                if(i == 3 && tempX >= 1 && tempX <= N && tempY >= 1 && tempY <= M 
                        && maze[tempX][tempY] == 0){ // 아래 위 옆 방향 다 봤는데 갈 데가 없으면
                    pop(stack);
                    pop(stack);
                }
            }
                 
        }
    }
     
    public static void main(String[] args) {
        // TODO Auto-generated method stub
 
        Scanner in = new Scanner(System.in);
         
        int N = in.nextInt();
        int M = in.nextInt();
         
        int maze[][] = new int[N+2][M+2];
        int visit[][] = new int[N+2][M+2];
        String tp[] = new String[N];
         
        for(int i = 0; i < N; i ++){
            tp[i] = in.next();
        }
         
        for(int i = 0; i < N+2; i ++){
            for(int j = 0; j < M+2; j ++){
                if(i == 0 || i == N+1 || j == 0 || j == M+1){
                    maze[i][j] = 0;
                    visit[i][j] = 1;
                }
                else {
                    maze[i][j] = (int)tp[i-1].charAt(j-1) - 48;
                    visit[i][j] = 0;
                }
            }
        }
         
        DFS(N, M, maze, visit);
         
     
         
         
    }
 
}

zlzmsrhak 6년 전 1

45번째 줄에서 스택의 가장 위에서 2번째 숫자를 가져와야 하는데, 가장 위에 있는 숫자를 가져와서 문제가 생기는 것 같습니다.

되도록이면 귀찮더라도 숫자 2개로 이루어진 클래스 하나를 정의해서 사용하는 것이 좋은 것 같습니다.

cakimmy24 6년 전 0

아하 그렇군요!!! 무엇이 잘못됐는지 알겠습니다 감사합니다 ^^

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

문제

문제

출처

ICPC

stack으로 구현한 dfs알고리즘 좀 봐주세요 ㅠㅠ

cakimmy24 6년 전 0

zlzmsrhak 6년 전 1

cakimmy24 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말