[백준] C++ 1697번:숨바꼭질

최단경로 문제의 경우 저의 경우 bfs가 익숙해져서 bfs로 대부분 문제를 푸는 편입니다.

 

 

풀이)

n위치에 있는 수빈이가 k위치에 있는 동생에게 최단시간에 가는 시간을 구하는 문제입니다.

가는 방향의 경우, x-1, x+1, x*2  이렇게 3가지 경우가 있으며 보통의 bfs 문제와 다르게 이 문제는 x좌표만 고려해주면 되기때문에 쉬운 편입니다. 

 

풀이의 경우 이번에는 제가 푼 코드와 gpt로 다듬은 코드를 두개 다 보여드리겠습니다...

BFS문제의 경우 제대로 2~3문제를 풀고 나면, 그 뒤부터는 어떤 문제가 와도 쉽게 넘어갈 수 있기 때문에

확실하게 해두는 것이 좋을 것 같습니다. 우선 제 코드 입니다.

 

코드1)

#include<iostream>
#include<queue>
using namespace std;


const int MAX = 100'001;
int visited[MAX];
int cnt{};

void bfs(int start, int end) {
	queue<int > q;
	q.push(start);
	visited[start] = true;

	while (not q.empty()) {

		int x = q.front();
		q.pop();

		int nx = x * 2;
		if (0 <= nx && nx <= MAX && not visited[nx]) {
			q.push(nx);
			visited[nx] = visited[x] + 1;
		}
		nx = x - 1;
		
		if (0 <= nx && nx <= MAX && not visited[nx]) {
			q.push(nx);
			visited[nx] = visited[x] + 1;
		}
		
		nx = x + 1;
		if (0 <= nx && nx <= MAX && not visited[nx]) {
			q.push(nx);
			visited[nx] = visited[x] + 1;
		}
	}
}



int main()
{
	int n, k;
	cin >> n >> k;
	//수빈 위치 n  동생 위치 k
	//수빈 -> 동생을 찾아가야됨 

	//가장 빠른 시간이 몇초인지  x-1, x+1위치로 이동, or 순간이동 x*2


	bfs(n, k);

	cout << visited[k] - 1;



}

제 블로그를 기존에 보셨던 분들은 제가 함수이름 네이밍 하는게 익숙하셔서 이게 편하실 수 있으시겠지만,

이 부분에서 같은 코드가 계속 들어간 다는 점이 좀 보기 불편해서 보기편한 코드로 gpt님의 도움을 받아 바꾸어 보았습니다.

이 코드가 확실히 더 간결하고 좋은 것 같죠?

 

코드2)

gpt가 이렇게 다듬어 주더군요

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int MAX_POSITION = 100001; // 위치의 최대 범위 [0, 100000]
vector<int> visited(MAX_POSITION, 0); // 방문 시간 저장 (0으로 초기화)

// 최단 시간을 계산하는 함수
int find_min_time(int start, int target) {
    queue<int> positions;
    positions.push(start);
    visited[start] = 1; // 시작 위치의 시간은 1로 설정 (0초부터 시작)

    while (!positions.empty()) {
        int current = positions.front();
        positions.pop();

        // 동생 위치에 도달하면 최단 시간 반환
        if (current == target) return visited[current] - 1;

        // 이동 가능한 위치 계산 (순간 이동, 앞으로 이동, 뒤로 이동)
        for (int next_position : {current * 2, current - 1, current + 1}) {
            // 유효 범위 내에서 미방문 위치만 처리
            if (next_position >= 0 && next_position < MAX_POSITION && visited[next_position] == 0) {
                positions.push(next_position);
                visited[next_position] = visited[current] + 1; // 이전 위치에서 1초 추가
            }
        }
    }
}

int main() {
    int n, k;
    cin >> n >> k; // 수빈 위치 n, 동생 위치 k

    cout << find_min_time(n, k);
}

속도의 경우 동일하니, 두 코드를 보시고  bfs를 연습하시는 분은 더 읽기 쉬운 코드로 연습하면 좋을 것 같습니다.

 

 

잡다한얘기)

졸작만든답시고 1년간 모델링배우고 데디서버에 이것저것 잡다한 것들에 집중해서 한동안 침체기였는데

이제 다 끝나고 시간이 요즘 남아서 꾸준히 푸니까 다시 금방 느는 것 같네요.. 

하기 힘든날에는 쉬운문제라도 하루에 하나씩 하시는걸 정말 추천 드립니다.. (그러지 못한 1인)

 

저는 올해 9월전에 플래티넘을 목표로 달려볼까 합니다 다들 화이팅..