[백준(BOJ)] 18513번 : 샘터 - C++[CPP]

https://www.acmicpc.net/problem/18513

18513번: 샘터

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

---

 

⊙ 문제 접근 과정

 

같은 거리의 집을 다 탐색하고도 탐색할 집이 남아있다면 거리를 1 늘리고 다시 탐색한다.

 

set을 이용하여 방문을 했는지 안 했는지 판별했다.

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <queue>
#include <set>

using namespace std;
typedef long long ll;

int K, N;
ll misfortune=1, result=0;
int dx[]={1,-1};
queue<int> q;
set<int> s;

ll bfs() {
    while(!q.empty()) {
        int Size = q.size(); //size가 계속 변할 수 있으므로 고정해준다
        for(int i=0; i<Size;i++) { //size만큼 반복
            int a = q.front();
            q.pop();
            for(int j=0;j<2;j++) {
                int nx = a + dx[j]; //좌우 탐색
                if(!s.count(nx)) { //값이 없다면
                    s.insert(nx); q.push(nx);//추가
                    result+=misfortune;//불행도 갱신

                    if(!--K) return result;//모든 집을 지었다면 종료
                }
            }
        }
        misfortune++; //동일한 거리 다 했으니 1 증가 후 증가한만큼의 거리, 다시 탐색
    }
    return result;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> N >> K;
    
    for(int i=0;i<N;i++) {
        int x;
        cin >> x;
        q.push(x); s.insert(x);
    }
    cout << bfs();
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

bfs 그렇게 많이 했는데 아직도 어렵다.

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!