글 읽기 - DFS 풀이 시 방문처리

belita76 3년 전 0

1) 현재 위치가 목적지 인지 확인

2) 현재 위치가 목적지가 아니면 위로 이동 / 아래로 이동

위의 로직을 DFS로 구현했을 때 방문처리에 관해 질문드립니다.

방문 처리를 "다음 위치로 이동하기 전 다음 위치 방문 표시"

이렇게 하면 틀리다고 나오는데,

"현재위치를 방문 표기" 로 하면 맞았다고 됩니다.

혹시 두 로직의 차이가 무엇인지 알 수 있을까요?

// 다음 방문위치 방문 표시 (틀림)
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static int F;
    public static int S;
    public static int G;
    public static int U;
    public static int D;
    public static boolean[] floor;
    public static int minButtonCount = 1000000;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        F = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        G = Integer.parseInt(st.nextToken());
        U = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        floor = new boolean[F+1];

        floor[S] = true;
        getMinButtonCount(S ,0);

        bw.write(String.valueOf(minButtonCount));
        bw.flush();


    }

    //currentFloor에서 G로 이동하는 최소 횟수
    public static void getMinButtonCount(int currentFloor, int count){
        if(currentFloor==G){
            minButtonCount = Math.min(minButtonCount, count);

        }
        else{
            int nextUpFloor =currentFloor + U;
            int nextDownFloor = currentFloor -D;

            if(nextUpFloor<=F && !floor[nextUpFloor]){
                floor[nextUpFloor] = true;
                getMinButtonCount(nextUpFloor, count+1);
            }

            if(nextDownFloor>=1 &&!floor[nextDownFloor] ){
                floor[nextDownFloor] = true;
                getMinButtonCount(nextDownFloor, count+1);
            }
        }

    }
}

/*
 ****************************************************************************************
*/

//현재위치 방문표시 (맞음)
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static int F;
    public static int S;
    public static int G;
    public static int U;
    public static int D;
    public static boolean[] floor;
    public static int minButtonCount =  1000001;
    public static boolean isFound = false;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        F = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        G = Integer.parseInt(st.nextToken());
        U = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        floor = new boolean[1000001];

        floor[S] = true;
        getMinButtonCount(S ,0);


        if(!isFound){
            bw.write("use the stairs");
        }
        else{
            bw.write(String.valueOf(minButtonCount));
        }
        bw.flush();


    }

    //currentFloor에서 G로 이동하는 최소 횟수
    public static void getMinButtonCount(int currentFloor, int count){
        if(currentFloor==G){
            minButtonCount = Math.min(minButtonCount, count);
            isFound = true;
        }
        else{
            floor[currentFloor] = true;
            int nextUpFloor =currentFloor + U;
            int nextDownFloor = currentFloor -D;

            if((nextUpFloor<=F && nextUpFloor>=1) && !floor[nextUpFloor]){
                getMinButtonCount(nextUpFloor, count+1);
            }

            if((nextDownFloor<=F && nextDownFloor>=1) && !floor[nextDownFloor] ){
                getMinButtonCount(nextDownFloor, count+1);
            }
        }

    }
}

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

문제

문제

출처

ICPC

DFS 풀이 시 방문처리

belita76 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말