#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
 
int N, M;
vector<int> v[10010];
vector<int> result;
int visited[10010];
int Max;
int cnt;
 
void DFS(int first, int start)
{
    if(Max < cnt)
    {
        Max = cnt;
        result.clear();
        result.push_back(first);    
    }
    else if(Max == cnt)
    {
        result.push_back(first);
    }
    
    for(int i = 0; i < v[start].size(); i++)
    {        
        if(visited[v[start][i]] == 0)
        {
            visited[v[start][i]] = 1;
            cnt++;
            DFS(first, v[start][i]);
        }
    }
}
 
int main(void)
{
//    freopen("B1325_input.txt", "r", stdin);
    
    cin >> N >> M;
    
    for(int i = 1; i <= M; i++)
    {
        int from, to;
        cin >> from >> to;
        
        v[to].push_back(from);
    }
    
    for(int i = 1; i <= N; i++)
    {
        memset(visited, 0, sizeof(visited));
        cnt = 1;
        visited[i] = 1;
        DFS(i, i);
    }
    
    sort(result.begin(), result.end());
    for(int i = 0; i < result.size(); i++)
    {
        cout << result[i] << " ";
    }
        
    return 0;
}
cs
저작자표시

'Baekjoon > DFS' 카테고리의 다른 글

[백준 17779] 게리맨더링2 (DFS) (C/C+) (★)  (0) 2021.01.17
[백준 1068] 트리 (DFS, Tree) (C/C++) (★)  (0) 2020.02.16
[백준 9466] 텀 프로젝트 (DFS) (C/C++) (★★★)  (0) 2020.01.26
[백준 2667] 단지번호 붙이기 (DFS) (C/C++)  (0) 2020.01.26
[백준 10451] 순열 사이클 (DFS) (C/C++)  (0) 2020.01.26
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string>
#include <string.h>
using namespace std;
 
typedef struct dNode
{
    int x;
    int y;
    int dirtyNum;
}dNode;
 
typedef struct qNode
{
    int x;
    int y;
    int clearDirty;
    int dist;
}qNode;
 
char Map[25][25];
int visited[25][25][1 << 11];
int row, col;
vector<dNode> dirty;
int dirtyCnt;
int clear;
int ans = -1;
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < row && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS()
{
    queue<qNode> q;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(Map[i][j] == 'o')
            {
                q.push({i, j, 0, 0});
                visited[i][j][0] = 1;
                break;
            }
        }
    }
    
    while(!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        int clearDirty = q.front().clearDirty;
        int dist = q.front().dist;
        q.pop();
        
        if(clear == clearDirty)
        {
            ans = dist;
            return;
        }
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            // 더러운 곳이 아닌 경우 
            if(safe(xpos, ypos) == 1 && Map[xpos][ypos] != '*' && Map[xpos][ypos] != 'x' && visited[xpos][ypos][clearDirty] == 0)
            {
                visited[xpos][ypos][clearDirty] = 1;
                q.push({xpos, ypos, clearDirty, dist+1});
            } 
            // 더러운 곳인 경우 
            else if(safe(xpos, ypos) == 1 && Map[xpos][ypos] == '*' && visited[xpos][ypos][clearDirty] == 0)
            {
                int findNum;
                
                for(int j = 0; j < dirty.size(); j++)
                {
                    if(dirty[j].x == xpos && dirty[j].y == ypos)
                    {
                        findNum = dirty[j].dirtyNum;
                        break;        
                    }
                }
                                
                // 깨끗하게 만들지 않은 칸이면
                if((clearDirty & (1 << findNum-1)) == 0)
                {
                    int tempClearDirty = clearDirty;
                    tempClearDirty += (1 << findNum-1);
                    
                    visited[xpos][ypos][tempClearDirty] = 1;
                    q.push({xpos, ypos, tempClearDirty, dist+1});
                }
                // 깨끗하게 만든 칸이면
                else
                {
                    visited[xpos][ypos][clearDirty] = 1;
                    q.push({xpos, ypos, clearDirty, dist+1});
                }     
            }
        }
    }
}
 
int main(void)
{
//    freopen("B4991_input.txt", "r", stdin);
    
    while(1)
    {
        memset(visited, 0, sizeof(visited));
        dirty.clear();
        dirtyCnt = 0;
        ans = -1;
        
        cin >> col >> row;
    
        if(row == 0 && col == 0)
        {
            return 0;
        }
        
        for(int i = 0; i < row; i++)
        {
            string temp;
            cin >> temp;
            
            for(int j = 0; j < temp.size(); j++)
            {
                Map[i][j] = temp[j];
                
                // 비트 연산을 위해 더러운 곳에 번호 부여 
                if(Map[i][j] == '*')
                {
                    dirty.push_back({i, j, ++dirtyCnt});
                }
            }
        }
        
        // 더러운 곳을 모두 채웠을 때의 비트 값 
        clear = (1 << dirtyCnt) - 1;
        
        BFS();
        
        cout << ans << endl;
    }
    
    return 0;
}
 cs
저작자표시

'Baekjoon > BFS' 카테고리의 다른 글

[백준 5213] 과외맨 (BFS) (C/C++) (★★)  (0) 2020.05.26
[백준 1939] 중량제한 (BFS, BinarySearch) (C/C++) (★★★)  (0) 2020.05.24
[백준 2638] 치즈 (BFS) (C/C++) (★★★)  (0) 2020.04.07
[백준 2589] 보물섬 (BFS) (C/C++)  (0) 2020.04.07
[백준 1938] 통나무 옮기기 (BFS) (C/C++) (★★★)  (0) 2020.02.19
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
using namespace std;
 
int N, M;
vector<pair<int, int>> pos;
double v[1010][1010];
int visited[1010];
double cost;
 
void prim()
{    
    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
    visited[1] = 1;    
    for(int i = 2; i <= N; i++)
    {
        int next = i;
        double nextCost = v[1][i];
        
        pq.push({nextCost, next});
    }
    
    while(!pq.empty())
    {
        int now = pq.top().second;
        double nowCost = pq.top().first;        
        pq.pop();
        
        if(visited[now] == 0)
        {
            visited[now] = 1;
            cost += nowCost;
        } 
        else
        {
            continue;
        }
        
        for(int i = 1; i <= N; i++)
        {
            int next = i;
            double nextCost = v[now][i];
            
            if(visited[next] == 0)
            {
                pq.push({nextCost, next});
            }
        }
    }
}
 
int main(void)
{
//    freopen("B1774_input.txt", "r", stdin);
    
    cin >> N >> M;
    
    for(int i = 1; i <= N; i++)
    {
        int x, y;
        cin >> x >> y;
        
        pos.push_back({x, y});    
    }
    
    for(int i = 0; i < pos.size(); i++)
    {
        for(int j = 0; j < pos.size(); j++)
        {
            if(i == j)
            {
                continue;
            }
            
            double weight = sqrt(pow(pos[i].first-pos[j].first, 2.0) + pow(pos[i].second-pos[j].second, 2.0));    
            
            v[i+1][j+1] = weight;
        }
    }
    
    for(int i = 1; i <= M; i++)
    {
        int from, to;
        cin >> from >> to;
        
        // 연결된 정점의 비용을 0으로 초기화 
        v[from][to] = 0;
        v[to][from] = 0;
    }
 
    prim();
    
    printf("%.2lf", cost);
        
    return 0;
}
cs
저작자표시

'Baekjoon > MST' 카테고리의 다른 글

[백준 1197] 최소 스패닝 트리 (Prim) (C/C++)  (0) 2020.05.17
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;
 
int V, E;
vector<pair<int, int>> v[10010];
int visited[10010];
int cost;
 
void prim()
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    visited[1] = 1;
    for(int i = 0; i < v[1].size(); i++)
    {
        pq.push({v[1][i].second, v[1][i].first});
    }
    
    while(!pq.empty())
    {
        int now = pq.top().second;
        int nowCost = pq.top().first;        
        pq.pop();
        
        if(visited[now] == 0)
        {
            visited[now] = 1;
            cost += nowCost;
        }
        else
        {
            continue;
        }
        
        for(int i = 0; i < v[now].size(); i++)
        {
            int next = v[now][i].first;
            int nextCost = v[now][i].second;
            
            if(visited[next] == 0)
            {
                pq.push({nextCost, next});
            }
        }
    }
}
 
int main(void)
{
//    freopen("B1197_input.txt", "r", stdin);
    
    cin >> V >> E;
    
    for(int i = 1; i <= E; i++)
    {
        int from, to, weight;
        cin >> from >> to >> weight;
        
        // 양방향 삽입 
        v[from].push_back({to, weight});
        v[to].push_back({from, weight});    
    }
    
    prim();
    
    cout << cost << endl;
    
    return 0;
}
cs
저작자표시

'Baekjoon > MST' 카테고리의 다른 글

[백준 1774] 우주선과의 교감 (Prim) (C/C++) (★★)  (0) 2020.05.18
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;
 
int N, M;
vector<pair<int, int>> v[20010];
int d[20010];
int Max;
int MaxIdx;
int MaxNum;
 
void dijkstra()
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, 1}); // {비용, 정점}
    d[1] = 0;
    
    while(!pq.empty())
    {
        int now = pq.top().second;
        int nowCost = pq.top().first;        
        pq.pop();
        
        // 최소비용 아니면 패스 
        if(d[now] != nowCost)
        {
            continue;
        } 
        
        for(int i = 0; i < v[now].size(); i++)
        {
            int next = v[now][i].first;
            int nextCost = v[now][i].second; 
            
            if(d[next] > d[now] + nextCost)
            {
                d[next] = d[now] + nextCost;
                pq.push({d[next], next});
            }
        }
    }
}
 
int main(void)
{
//    freopen("B6118_input.txt", "r", stdin);
    
    cin >> N >> M;
    
    for(int i = 2; i <= N; i++)
    {
        d[i] = 99999999;
    }
    
    for(int i = 1; i <= M; i++)
    {
        int from, to;
        cin >> from >> to;
        
        // 양방향 삽입 
        v[from].push_back({to, 1});
        v[to].push_back({from, 1});    
    }
    
    dijkstra();
 
    for(int i = 2; i <= N; i++)
    {
        if(d[i] > Max)
        {
            Max = d[i];
            MaxIdx = i;
        }
    }
    
    for(int i = 2; i <= N; i++)
    {
        if(Max == d[i])
        {
            MaxNum++;
        }
    }
    
    cout << MaxIdx << " " << Max << " " << MaxNum;
    
    return 0;
}
cs
저작자표시

'Baekjoon > Graph' 카테고리의 다른 글

[백준 5719] 거의 최단경로 (Dijkstra) (C/C++) (★★★)  (0) 2020.02.19
[백준 16681] 등산 (Dijkstra) (C/C++) (★★)  (0) 2020.02.18
[백준 2211] 네트워크 복구 (Dijkstra) (C/C++)  (0) 2020.02.18
[백준 1504] 특정한 최단경로 (Floyd-Warshall) (C/C++)  (0) 2020.02.17
[백준 1238] 파티 (Floyd-Warshall) (C/C++)  (0) 2020.02.17
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
 
int N;
int map[25][25];
int mapCopy[25][25];
int candidate[10];
int Max;
 
void reset()
{
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            map[i][j] = mapCopy[i][j];
        }
    }
}
 
int find()
{
    int val = 0;
    
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            if(val < map[i][j])
            {
                val = map[i][j];
            }
        }
    }
    
    return val;
}
 
void move()
{
    for(int k = 0; k < 5; k++)
    {        
        // 오른쪽 
        if(candidate[k] == 0)
        {
            for(int i = 1; i <= N; i++)
            {
                deque<int> q;        // 유효한 숫자만 저장하는 덱 -> 0은 저장X 
                bool merge = false; // 이미 합쳐졌던 블록인지 확인 
                
                for(int j = N; j >= 1; j--)
                {
                    // 마지막 숫자와 현재 숫자가 같으면 합침 + 전에 합쳐진 블록이 아니면
                    if(q.size() >= 1 && q[q.size()-1] == map[i][j] && merge == false)
                    {
                        q[q.size()-1] += map[i][j];
                        merge = true;
                    }
                    // 0인 경우는 저장X 
                    else if(map[i][j] != 0)
                    {
                        q.push_back(map[i][j]);        
                        merge = false;
                    }
                }        
                
                for(int j = N; j >= 1; j--)
                {
                    // 유효한 숫자가 있는 구간에서는 차례대로 넣어줌 
                    if(q.size() >= 1)
                    {
                        map[i][j] = q.front();
                        q.pop_front();
                    }
                    // 유효한 숫자가 아닌 구간에서는 0을 넣어줌 
                    else
                    {
                        map[i][j] = 0;
                    }
                }
            } 
        }
        // 왼쪽
        else if(candidate[k] == 1)
        {        
            for(int i = 1; i <= N; i++)
            {
                deque<int> q;        
                bool merge = false; 
            
                for(int j = 1; j <= N; j++)
                {
                    if(q.size() >= 1 && q[q.size()-1] == map[i][j] && merge == false)
                    {
                        q[q.size()-1] += map[i][j];
                        merge = true;
                    }
                    else if(map[i][j] != 0)
                    {
                        q.push_back(map[i][j]);        
                        merge = false;
                    }
                }        
                
                for(int j = 1; j <= N; j++)
                {
                    if(q.size() >= 1)
                    {
                        map[i][j] = q.front();
                        q.pop_front();
                    }
                    else
                    {
                        map[i][j] = 0;
                    }
                }
            } 
        } 
        // 위쪽 
        else if(candidate[k] == 2)
        {                
            for(int j = 1; j <= N; j++)
            {
                deque<int> q;
                bool merge = false;
            
                for(int i = 1; i <= N; i++)
                {
                    if(q.size() >= 1 && q[q.size()-1] == map[i][j] && merge == false)
                    {
                        q[q.size()-1] += map[i][j];
                        merge = true;
                    }
                    else if(map[i][j] != 0)
                    {
                        q.push_back(map[i][j]);        
                        merge = false;
                    }
                }        
                
                for(int i = 1; i <= N; i++)
                {
                    if(q.size() >= 1)
                    {
                        map[i][j] = q.front();
                        q.pop_front();
                    }
                    else
                    {
                        map[i][j] = 0;
                    }
                }
            } 
        }
        // 아래쪽 
        else if(candidate[k] == 3)
        {
            for(int j = 1; j <= N; j++)
            {
                deque<int> q;
                bool merge = false;
            
                for(int i = N; i >= 1; i--)
                {
                    if(q.size() >= 1 && q[q.size()-1] == map[i][j] && merge == false)
                    {
                        q[q.size()-1] += map[i][j];
                        merge = true;
                    }
                    else if(map[i][j] != 0)
                    {
                        q.push_back(map[i][j]);        
                        merge = false;
                    }
                }        
                
                for(int i = N; i >= 1; i--)
                {
                    if(q.size() >= 1)
                    {
                        map[i][j] = q.front();
                        q.pop_front();
                    }
                    else
                    {
                        map[i][j] = 0;
                    }
                }
            } 
        }
    }
}
 
void permutation(int cnt)
{
    if(cnt == 5)
    {
        // 이동 
        move();
        
        // 최댓값 확인 
        Max = max(Max, find());
        
        // 리셋 
        reset();
        
        return;
    }
    
    for(int i = 0; i < 4; i++)
    {
        candidate[cnt] = i;
        permutation(cnt+1);
    }
}
 
 
int main(void)
{
//    freopen("B12100_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            cin >> map[i][j];
            mapCopy[i][j] = map[i][j];
        }
    }
    
    permutation(0);
    
    cout << Max << endl;
 
    return 0;
}
cs
저작자표시

'Baekjoon > Simulation' 카테고리의 다른 글

[백준 13458] 시험감독 (Simulation) (C/C++)  (0) 2020.04.09
[백준 14891] 톱니바퀴 (Simulation) (C/C++) (★)  (0) 2020.04.09
[백준 16235] 나무 재테크 (Simulation) (C/C++) (★)  (0) 2020.03.27
[백준 15685] 드래곤 커브 (Simulation) (C/C++) (★★)  (0) 2020.03.27
[백준 14890] 경사로 (Simulation) (C/C++) (★★)  (0) 2020.03.27
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int cal(vector<int> rocks, int mid, int distance)
{
    int cnt = 0;
    int prev = 0;
    
    for(int i = 0; i < rocks.size(); i++)
    {
        if(rocks[i] - prev < mid)
        {
            cnt++;
        }
        else
        {
            prev = rocks[i];
        }
    }
    
    // 도착지점과 마지막 돌 체크
    if(distance - prev < mid)
    {
        cnt++;
    }
    
    return cnt;
}
 
int solution(int distance, vector<int> rocks, int n) 
{
    int Max = 0;
    int left = 1;
    int right = distance;
    
    sort(rocks.begin(), rocks.end());
    
    while(left <= right)
    {
        // 바위 사이 거리의 최솟값
        int mid = (left + right) / 2;
        
        if(cal(rocks, mid, distance) > n)
        {
            right = mid-1;
        }
        else
        {
            left = mid+1;
            
            if(mid > Max)
            {
                Max = mid;
            }
        }
    }
    
    return Max;
}
cs
저작자표시

'Programmers > Level 4' 카테고리의 다른 글

[프로그래머스 4] 4단 고음 (C/C++) (★★★)  (0) 2020.03.11
[프로그래머스 4] 블록 게임 (C/C++) (★★)  (0) 2020.03.05
[프로그래머스 4] 카드게임 (C/C++) (★★)  (0) 2020.01.15
[프로그래머스 4] 도둑질 (C/C++) (★)  (0) 2020.01.15
#include <string>
#include <vector>
#include <iostream>
using namespace std;
 
bool cal(vector<int> stones, int mid, int k)
{
    int cnt = 0;
    
    for(int i = 0; i < stones.size(); i++)
    {
        if(stones[i] - mid <= 0)
        {
            cnt++;
        }
        else
        {
            cnt = 0;
        }
        
        if(cnt >= k)
        {
            return true;
        }
    }
    
    return false;
}
 
int solution(vector<int> stones, int k) 
{
    int answer = 0;
    int left = 1;
    int right = 200000000;
    int Max = 0;
    
    while(left <= right)
    {
        // 친구의 수
        int mid = (left + right) / 2;
        
        if(cal(stones, mid, k))
        {
            right = mid-1;
        }
        else
        {
            left = mid+1;
            
            // 연속된 (stone - 친구 == 0) 부분이 k개 미만인 최댓값 구하기
            if(Max < mid)
            {
                Max = mid;
            }
        }
    }
    
    // 연속된 (stone - 친구 == 0) 부분이 k개 이상이려면 최댓값+1
    return Max+1;
}
cs
저작자표시

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 블록 이동하기 (C/C++) (★★)  (0) 2020.03.11
[프로그래머스 3] GPS (C/C++) (★★★★)  (0) 2020.03.11
[프로그래머스 3] 리틀 프렌즈 사천성 (C/C++) (★★)  (0) 2020.03.10
[프로그래머스 3] 방문 길이 (C/C++)  (0) 2020.03.09
[프로그래머스 3] 숫자 게임 (C/C++)  (0) 2020.03.09

+ Recent posts

티스토리툴바