백준: 스타트링크

김아무개·2023년 4월 7일

다시 풀어볼 문제

목록 보기

4/8

ChatGPT 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int F, S, G, U, D;
    static int[] visited;

    public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());

        visited = new int[F + 1];

        bfs();

        if (visited[G] == 0) {
            System.out.println("use the stairs");
        } else {
            System.out.println(visited[G] - 1);
        }
    }
    
    public static void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(S);
        visited[S] = 1;

        while (!queue.isEmpty()) {
            int current = queue.poll();

            if (current == G) {
                break;
            }

            int up = current + U;
            int down = current - D;

            if (up <= F && visited[up] == 0) {
                queue.offer(up);
                visited[up] = visited[current] + 1;
            }

            if (down >= 1 && visited[down] == 0) {
                queue.offer(down);
                visited[down] = visited[current] + 1;
            }
        }
    }
}

이 문제는 왠지 풀 수 있을것 같아서 (단순해 보여서)
호기롭게 도전했다가 호되게 실패한 문제다.🥲

이걸 미처 확인하지 못함...🥲

그래서 ChatGPT에게 도움을 요청해봤다.
그런데 GPT가 한방에 해냄........!!!!!!

🤓📝

BFS를 사용한 이유

이 문제를 BFS(너비 우선 탐색)로 푼 이유는 다음과 같습니다:

1. 최소 이동 횟수 찾기

BFS는 최단 경로 문제에서 최소 이동 횟수를 찾는 데 적합한 알고리즘입니다.
각 단계에서 가능한 모든 층을 방문하며, 최소 버튼 클릭 횟수를 찾습니다.
이 문제의 경우, U와 D 버튼을 사용하여 엘리베이터가 도달할 수 있는 층을 찾아야 하며, BFS는 이러한 목적에 적합합니다.

2. 방문한 층 추적

BFS를 사용하면 각 단계에서 방문한 층을 쉽게 추적할 수 있습니다.
visited 배열을 사용하여 각 층의 방문 여부를 기록하고, 이를 통해 중복 방문을 방지할 수 있습니다.
이는 문제의 효율성을 높이고, 필요한 최소 클릭 횟수를 찾는 데 도움이 됩니다.

3. 구현의 간결성

BFS를 사용하면 구현이 상대적으로 간결하고 이해하기 쉽습니다.
각 단계에서 가능한 모든 층을 방문하며, 도달할 수 없는 층이 있는지 확인하는 과정을 반복합니다.
이는 코드를 작성하고 디버깅하는 데 도움이 됩니다.

🤓📝

소스 코드 분석

1. 변수 생성, 초기화

// 전역 변수 선언
static int F, S, G, U, D;
static int[] visited;

// main ()
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
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()); // 내려가는 층 단위 개수

// 방문한 층에 누적 이동수 저장 
// 사용할 인덱스 : 1 ~ F
visited = new int[F + 1];

// bfs
bfs()

// 결과 출력
if (visited[G] == 0) {
	// 목표층에 방문을 못했으면 문장 출력
    System.out.println("use the stairs"); 
} else {
	// 시작 층도 카운팅 되서 1 빼줌
    System.out.println(visited[G]); 
}

2. bfs() 메서드 구현

public static void bfs() {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(S); // 시작 층 q에 입력
		visited[S] = 1; // 방문을 체크할 visited의 시작층에 1입력 -> 중복 방문 방지 (최소 방문 횟수 찾기 위함)
		
		while (!queue.isEmpty()) {
		    int current = queue.poll(); // 현재 층 = 큐에서 값을 꺼냄
		
			// 현재 층이 목표층이면 멈춤
		    if (current == G) { 
		        break;
		    }
		
		    int up = current + U;   // 위로 올라가게 되면 현재층 + up 층
		    int down = current - D; // 아래로 내려가게 되면 현재층 - down 층
		
		    // 위로 올라갔을 때 top층 이하에 있고, up 층에 최초 방문이면
		    if (up <= F && visited[up] == 0) {
		        queue.offer(up); // 큐에 up층 집에 넣음
		        visited[up] = visited[current] + 1; // up층에 누적 이동횟수 1증가시켜서 저장
		    }

				// 내려갔을 때 1층 이상에 있고, down층에 최초 방문이면
		    if (down >= 1 && visited[down] == 0) {
		        queue.offer(down); // 큐에 down층 집에 넣음
		        visited[down] = visited[current] + 1; // 방문배열의 down 인덱스에 현재 층 인덱스의 값에서 1을 더해 넣음(= 총 이동 횟수. 층 상관x)
		    }
		}
}