๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๐Ÿ“ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Programmers

[C++/PGS] Lv.3 : ๊ฐ€์žฅ ๋จผ ๋…ธ๋“œ (๊ทธ๋ž˜ํ”„/bfs)

728x90

https://school.programmers.co.kr/learn/courses/30/lessons/49189

 

๋ฌธ์ œ ์„ค๋ช…

n๊ฐœ์˜ ๋…ธ๋“œ๊ฐ€ ์žˆ๋Š” ๊ทธ๋ž˜ํ”„๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฐ ๋…ธ๋“œ๋Š” 1๋ถ€ํ„ฐ n๊นŒ์ง€ ๋ฒˆํ˜ธ๊ฐ€ ์ ํ˜€์žˆ์Šต๋‹ˆ๋‹ค. 1๋ฒˆ ๋…ธ๋“œ์—์„œ ๊ฐ€์žฅ ๋ฉ€๋ฆฌ ๋–จ์–ด์ง„ ๋…ธ๋“œ์˜ ๊ฐฏ์ˆ˜๋ฅผ ๊ตฌํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๊ฐ€์žฅ ๋ฉ€๋ฆฌ ๋–จ์–ด์ง„ ๋…ธ๋“œ๋ž€ ์ตœ๋‹จ๊ฒฝ๋กœ๋กœ ์ด๋™ํ–ˆ์„ ๋•Œ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜๊ฐ€ ๊ฐ€์žฅ ๋งŽ์€ ๋…ธ๋“œ๋“ค์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.

๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜ n, ๊ฐ„์„ ์— ๋Œ€ํ•œ ์ •๋ณด๊ฐ€ ๋‹ด๊ธด 2์ฐจ์› ๋ฐฐ์—ด vertex๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, 1๋ฒˆ ๋…ธ๋“œ๋กœ๋ถ€ํ„ฐ ๊ฐ€์žฅ ๋ฉ€๋ฆฌ ๋–จ์–ด์ง„ ๋…ธ๋“œ๊ฐ€ ๋ช‡ ๊ฐœ์ธ์ง€๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”.

 

์ œํ•œ์‚ฌํ•ญ
  • ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜ n์€ 2 ์ด์ƒ 20,000 ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • ๊ฐ„์„ ์€ ์–‘๋ฐฉํ–ฅ์ด๋ฉฐ ์ด 1๊ฐœ ์ด์ƒ 50,000๊ฐœ ์ดํ•˜์˜ ๊ฐ„์„ ์ด ์žˆ์Šต๋‹ˆ๋‹ค.
  • vertex ๋ฐฐ์—ด ๊ฐ ํ–‰ [a, b]๋Š” a๋ฒˆ ๋…ธ๋“œ์™€ b๋ฒˆ ๋…ธ๋“œ ์‚ฌ์ด์— ๊ฐ„์„ ์ด ์žˆ๋‹ค๋Š” ์˜๋ฏธ์ž…๋‹ˆ๋‹ค.

 

๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค

๊ฐ€์žฅ ๋จผ ๋…ธ๋“œ๋ฅผ ๋ฌผ์–ด๋ดค์œผ๋ฏ€๋กœ, ์ผ๋‹จ matrix์— ๋„ฃ๊ณ  ๋ฌด์ง€์„ฑ bfs ์‹คํ–‰.

๊ทธ๋ฆฌ๊ณ  ๊ทธ ๋…ธ๋“œ๊นŒ์ง€ ๊ฐ€๋ ค๋ฉด ๋ช‡ ๊ฐœ์˜ ๋…ธ๋“œ๋ฅผ ๊ฑฐ์ณ์•ผ ํ•˜๋Š”์ง€ answer ๋ฐฐ์—ด์— ์ €์žฅํ•˜์˜€์Šต๋‹ˆ๋‹ค.

 

bfs ํƒ์ƒ‰์ด ์ข…๋ฃŒ๋œ ํ›„, answer์„ ์ •๋ ฌํ•˜๊ณ  ์ตœ๋Œ€๊ฐ’์ด ๋ช‡ ๊ฐœ์ธ์ง€ ์„ธ์–ด๋ณด๋ฉด ๋!

 

 

 

๋‚˜์˜ ํ’€์ด

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int mat[20001][20001]={0};
int visited[20001]={0};
int answer[20001]={0};
int cnt=0;

bool canGo(int a, int i){
    if(visited[i]==1) return false;
    if(mat[a][i]==0) return false;
    return true;
}

void bfs(int n){
    queue<int> q;
    q.push(1);
    visited[1] = 1;
    answer[1] = 1;
    while(!q.empty()){
        int a = q.front();
        q.pop();
        for(int i=1; i<=20000; ++i){
            if(canGo(a,i)){
                visited[i] = 1;
                q.push(i);
                answer[i] = answer[a]+1;
            }
        }
    }
    sort(answer, answer+20001);
    int amax = answer[20000];
    for(int i=20000; i>=0; --i){
        if(answer[i] == amax) cnt++;
        else break;
    }
}

int solution(int n, vector<vector<int> > edge) {
    int ES = edge.size();
    for(int i=0; i<ES; ++i){
        mat[edge[i][0]][edge[i][1]] = 1;
        mat[edge[i][1]][edge[i][0]] = 1;
    }
    bfs(n);
    return cnt;
}

๋ฟŒ-๋“ฏ

 

728x90