#include <stdio.h>
#include <iostream>
#include <queue>
#include <map>
#include <string>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int N, M, K;
int road[400][400];
int dp[400][400];
 
int solve(int from, int cnt)
{
    // N에 도착시 종료 
    if(from == N)
    {
        return 0;
    }
    
    // M개의 도시를 전부돌았지만 최종 도착지가 N이 아니면 매우 작은 값 리턴  
    if(cnt >= M)
    {
        return -987654321;    
    }
    
    if(dp[from][cnt] != 0)
    {
        return dp[from][cnt];
    }
    dp[from][cnt] = -987654321;
    
    for(int to = from+1; to <= N; to++)
    {
        if(road[from][to] != 0)
        {
            dp[from][cnt] = max(dp[from][cnt], solve(to, cnt+1) + road[from][to]);
        }
    }
    
    return dp[from][cnt];
}
 
int main(void)
{
//    freopen("B2096_input.txt", "r", stdin);
    
    cin >> N >> M >> K;
    
    for(int i = 1; i <= K; i++)
    {
        int from, to, grade;
        cin >> from >> to >> grade;
        
        if(road[from][to] != 0)
        {
            road[from][to] = max(road[from][to], grade);    
        }
        else
        {
            road[from][to] = grade;
        }
    }
    
    cout << solve(1, 1) << "\n";
 
    return 0;
}
cs
저작자표시

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

[백준 2167] 2차원 배열의 합 (DP) (C/C++) (★★)  (0) 2020.05.28
[백준 1509] 팰린드롬 분할 (DP) (C/C++) (★★★)  (0) 2020.03.24
[백준 10942] 팰린드롬 ? (DP) (C/C++) (★★)  (0) 2020.03.23
[백준 11048] 이동하기 (DFS, DP) (C/C++) (★)  (0) 2020.03.23
[백준 1890] 점프 (DFS, DP) (C/C++)  (0) 2020.03.22
#include <iostream>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <string>
#include <string.h>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef struct node
{
    int x;
    int y;
    int cnt;
    int time;
}node;
 
int row, col, K;
int Map[1010][1010];
int visited[1010][1010][12][2];
int Min = 99999999;
 
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
 
int safe(int x, int y)
{
    if(1 <= x && x <= row && 1 <= y && y <= col)
    {
        return 1;
    }
    
    return 0;
}
 
void BFS()
{
    queue<node> q;
    
    q.push({1, 1, 0, 0});
    visited[1][1][0][0] = 1;
    
    while(!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        int cnt = q.front().cnt;
        int time = q.front().time;
        q.pop();
        
        if(x == row && y == col)
        {
            Min = visited[x][y][cnt][time];
            return;
        }
        
        for(int i = 0; i < 4; i++)
        {
            int nx = x+dx[i];
            int ny = y+dy[i];
            
            if(safe(nx, ny) == 0)
            {
                continue;
            }
            
            if(time == 0)
            {
                // 이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다.
                if(visited[x][y][cnt][1] == 0)
                {
                    q.push({x, y, cnt, 1});
                    visited[x][y][cnt][1] = visited[x][y][cnt][0] + 1;
                }
                
                if(Map[nx][ny] == 0 && visited[nx][ny][cnt][1] == 0)
                {
                    q.push({nx, ny, cnt, 1});
                    visited[nx][ny][cnt][1] = visited[x][y][cnt][0] + 1;
                }
                else if(Map[nx][ny] == 1 && visited[nx][ny][cnt+1][1] == 0 && cnt+1 <= K)
                {
                    q.push({nx, ny, cnt+1, 1});
                    visited[nx][ny][cnt+1][1] = visited[x][y][cnt][0] + 1;
                }
            }
            else if(time == 1)
            {
                // 이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다.
                if(visited[x][y][cnt][0] == 0)
                {
                    q.push({x, y, cnt, 0});
                    visited[x][y][cnt][0] = visited[x][y][cnt][1] + 1;
                }
                
                if(Map[nx][ny] == 0 && visited[nx][ny][cnt][0] == 0)
                {
                    q.push({nx, ny, cnt, 0});
                    visited[nx][ny][cnt][0] = visited[x][y][cnt][1] + 1;
                }
            }
        }    
    }
}
 
int main(void)
{
//    freopen("B14442_input.txt", "r", stdin);
    
    cin >> row >> col >> K;
    
    for(int i = 1; i <= row; i++)
    {
        for(int j = 1; j <= col; j++)
        {
            scanf("%1d", &Map[i][j]);
        }
    }
    
    BFS();
    
    if(Min == 99999999)
    {
        cout << "-1";
    }
    else
    {
        cout << Min;    
    }
    
    return 0;
}
cs
저작자표시

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

[백준 17471] 게리맨더링 (DFS) (C/C+) (★)  (0) 2021.01.17
[백준 5213] 과외맨 (BFS) (C/C++) (★★)  (0) 2020.05.26
[백준 1939] 중량제한 (BFS, BinarySearch) (C/C++) (★★★)  (0) 2020.05.24
[백준 4991] 로봇 청소기 (BFS, Bitmask) (C/C++) (★★★)  (0) 2020.05.21
[백준 2638] 치즈 (BFS) (C/C++) (★★★)  (0) 2020.04.07
#include <iostream>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <string>
#include <string.h>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int N;
int Map[25][25];
int visited[25][25];
int Min = 999999999;
 
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
 
int safe(int x, int y, int d1, int d2)
{
    if(1 <= x && x+d1+d2 <= N && 1 <= y-d1 && y+d2 <= N)
    {
        return 1;
    }
    
    return 0;
}
 
void color1234(int x, int y, int d1, int d2)
{
    for(int i = 1; i < x+d1; i++)
    {
        for(int j = 1; j <= y; j++)
        {
            if(visited[i][j] == 5)
            {
                break;
            }
            
            visited[i][j] = 1;
        }
    }
    
    for(int i = 1; i <= x+d2; i++)
    {
        for(int j = N; j > y; j--)
        {
            if(visited[i][j] == 5)
            {
                break;
            }
            
            visited[i][j] = 2;
        }
    }    
    
    for(int i = x+d1; i <= N; i++)
    {
        for(int j = 1; j < y-d1+d2; j++)
        {
            if(visited[i][j] == 5)
            {
                break;
            }
            
            visited[i][j] = 3;
        }
    }
 
    for(int i = x+d2+1; i <= N; i++)
    {
        for(int j = N; j >= y-d1+d2; j--)
        {
            if(visited[i][j] == 5)
            {
                break;
            }
            
            visited[i][j] = 4;
        }
    }
}
 
void color5(int x, int y, int d1, int d2)
{
    for(int i = 0; i <= d1; i++)
    {
        int nx = x + i;
        int ny = y - i;
        visited[nx][ny] = 5;
        
        nx = x + d2 + i;
        ny = y + d2 - i;
        visited[nx][ny] = 5;
    }
    
    for(int i = 0; i <= d2; i++)
    {
        int nx = x + i;
        int ny = y + i;
        visited[nx][ny] = 5;
        
        nx = x + d1 + i;
        ny = y - d1 + i;
        visited[nx][ny] = 5;
    }
}
 
void print()
{
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            cout << visited[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "\n";    
}
 
int cal()
{
    int sum[6] = {0};
    
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            if(visited[i][j] == 0 || visited[i][j] == 5)
            {
                sum[5] += Map[i][j];    
            }
            else
            {
                sum[visited[i][j]] += Map[i][j];
            }
        }
    }
    
    int Max = max({sum[1], sum[2], sum[3], sum[4], sum[5]});
    int Min = min({sum[1], sum[2], sum[3], sum[4], sum[5]});
    
    return Max - Min;
}
 
void solve()
{
    for(int x = 1; x <= N; x++)
    {
        for(int y = 1; y <= N; y++)
        {
            for(int d1 = 1; d1 <= N; d1++)
            {
                for(int d2 = 1; d2 <= N; d2++)
                {
                    if(safe(x, y, d1, d2) == 1)
                    {
                        memset(visited, 0, sizeof(visited));
                        
                        color5(x, y, d1, d2);
                        color1234(x, y, d1, d2);
                        
                        Min = min(Min, cal());
                    }
                }
            }
        }
    }
    
    cout << Min;
}
 
int main(void)
{
//    freopen("B17779_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            cin >> Map[i][j];
        }
    }
    
    solve();
    
    return 0;
}
cs
저작자표시

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

[백준 1325] 효율적인 해킹 (DFS) (C/C++) (★)  (0) 2020.05.24
[백준 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 <iostream>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <string>
#include <string.h>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int N;
int num[15];
vector<int> area[15];
vector<int> red;
int Min = 999999999;
 
int blue_check(vector<int> blue, int visited[15])
{
    queue<int> q;
    q.push(blue[0]);
    visited[blue[0]] = 1;
    int cnt = 1;
    
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        
        for(int i = 0; i < area[now].size(); i++)
        {
            int next = area[now][i];
            
            if(visited[next] == 0)
            {
                q.push(next);
                visited[next] = 1;
                cnt++;
            }
        }
    }
    
    if(cnt == blue.size())
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
int red_check(int visited[15])
{
    queue<int> q;
    q.push(red[0]);
    visited[red[0]] = 1;
    int cnt = 1;
    
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        
        for(int i = 0; i < area[now].size(); i++)
        {
            int next = area[now][i];
            
            if(visited[next] == 0)
            {
                q.push(next);
                visited[next] = 1;
                cnt++;
            }
        }    
    }
    
    if(cnt == red.size())
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void combination(int idx, int cnt, int finish)
{
    if(cnt == finish)
    {
        vector<int> blue;
        int red_visited[15] = {0};
        int blue_visited[15] = {0};
        int sum1 = 0;
        int sum2 = 0;
 
        for(int i = 0; i < red.size(); i++)
        {
            blue_visited[red[i]] = 1;
            sum1 += num[red[i]];
        }
        
        for(int i = 1; i <= N; i++)
        {
            if(blue_visited[i] == 0)
            {
                red_visited[i] = 1;
                blue.push_back(i);
                sum2 += num[i];
            }
        }
        
        if(red_check(red_visited) == 1)
        {
            if(blue_check(blue, blue_visited) == 1)
            {
                Min = min(Min, abs(sum1-sum2));
            }    
        }
        
        return;    
    }
    
    for(int i = idx; i <= N; i++)
    {
        red.push_back(i);
        combination(i+1, cnt+1, finish);
        red.pop_back();
    }
}
 
int main(void)
{
//    freopen("B17471_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> num[i];
    }
    
    for(int from = 1; from <= N; from++)
    {
        int M; 
        cin >> M;
        
        for(int i = 1; i <= M; i++)
        {
            int to;
            cin >> to;
            
            area[from].push_back(to);
            area[to].push_back(from);
        }
    }
    
    for(int i = 1; i <= N/2; i++)
    {
        combination(1, 0, i);
    }
    
    if(Min == 999999999)
    {
        cout << "-1";
    }
    else
    {
        cout << Min;    
    }
    
    return 0;
}
cs
저작자표시

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

[백준 16933] 벽 부수고 이동하기3 (BFS) (C/C+)  (0) 2021.01.19
[백준 5213] 과외맨 (BFS) (C/C++) (★★)  (0) 2020.05.26
[백준 1939] 중량제한 (BFS, BinarySearch) (C/C++) (★★★)  (0) 2020.05.24
[백준 4991] 로봇 청소기 (BFS, Bitmask) (C/C++) (★★★)  (0) 2020.05.21
[백준 2638] 치즈 (BFS) (C/C++) (★★★)  (0) 2020.04.07
#include <iostream>
#include <algorithm>
#include <math.h>
#include <algorithm>
using namespace std;
 
int N, M, K;
int arr[310][310];
long long dp[310][310];
int startX, startY;
int endX, endY;
 
int main(void)
{
//    freopen("B2167_input.txt", "r", stdin);
    
    cin >> N >> M;
    
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= M; j++)
        {
            cin >> arr[i][j];
        }
    }
    
    // 미리 구해놓기
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= M; j++)
        {
            dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1];        
        }
    } 
    
    cin >> K;
    
    for(int i = 1; i <= K; i++)
    {
        cin >> startX >> startY >> endX >> endY;
        
        // 좌표가 사각형 기준 오른쪽위, 왼쪽 아래인 경우 -> 왼쪽 위, 오른쪽 아래로 좌표 수정 
        int sx = min(startX, endX);
        int sy = min(startY, endY);
        int ex = max(startX, endX);
        int ey = max(startY, endY);
        
        cout << dp[ex][ey] - dp[sx-1][ey] - dp[ex][sy-1] + dp[sx-1][sy-1] << endl;
    }
    
    return 0;
}
cs
저작자표시

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

[백준 2157] 여행 (DP) (C/C++) (★★★)  (0) 2021.01.26
[백준 1509] 팰린드롬 분할 (DP) (C/C++) (★★★)  (0) 2020.03.24
[백준 10942] 팰린드롬 ? (DP) (C/C++) (★★)  (0) 2020.03.23
[백준 11048] 이동하기 (DFS, DP) (C/C++) (★)  (0) 2020.03.23
[백준 1890] 점프 (DFS, DP) (C/C++)  (0) 2020.03.22
#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
 
int N;
pair<int, int> Map[510][1020]; // 타일숫자, 타일번호 
int visited[510][1020];
int path[510*1020];
int tileNum;
int last; 
vector<int> trace;
 
int dx[4] = {-1, 1, 0, 0}; // 상하좌우 
int dy[4] = {0, 0, -1, 1}; // 상하좌우 
 
void BFS()
{
    queue<pair<int, int>> q;
    q.push({1, 1});
    q.push({1, 2});
    visited[1][1] = 1;
    visited[1][2] = 1;
    
    path[1] = 0; // 0번(초기화용 타일번호) -> 1번(시작 타일번호) 
    
    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
 
        if(Map[x][y].second == tileNum)
        {
//            cout << visited[x][y] << endl;
            last = Map[x][y].second;
            return;
        }
        else
        {
            last = max(last, Map[x][y].second);
        }
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(visited[xpos][ypos] != 0 || Map[xpos][ypos].first == 0 || Map[xpos][ypos].second == 0)
            {
                continue;
            }
            
            // (타일 번호가 다르고) 타일의 숫자가 같은 경우
            if(Map[x][y].second != Map[xpos][ypos].second && Map[x][y].first == Map[xpos][ypos].first)
            {
                q.push({xpos, ypos});
                visited[xpos][ypos] = visited[x][y]+1;
                path[Map[xpos][ypos].second] = Map[x][y].second;
                
                // 타일 번호가 같은 타일 숫자 왼쪽, 오른쪽 확인 후 큐에 삽입 
                if(Map[xpos][ypos-1].second == Map[xpos][ypos].second)
                {
                    q.push({xpos, ypos-1});    
                    visited[xpos][ypos-1] = visited[xpos][ypos];
                }
                else if(Map[xpos][ypos].second == Map[xpos][ypos+1].second)
                {
                    q.push({xpos, ypos+1});    
                    visited[xpos][ypos+1] = visited[xpos][ypos];
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B5213_input.txt", "r", stdin);
    
    cin >> N;
    
    int row = N;
    
    for(int k = 1; k <= row; k++)
    {
        // 홀수번째 row 
        if(k % 2 == 1)
        {
            for(int i = 1; i <= 2*N; i++)
            {
                if(i % 2 == 1)
                {
                    tileNum++;
                }
                
                int a;
                cin >> a;
                
                Map[k][i].first = a;
                Map[k][i].second = tileNum;
            }        
        }
        // 짝수번째 row
        else
        {
            for(int i = 2; i <= 2*N-1; i++)
            {
                if(i % 2 == 0)
                {
                    tileNum++;
                }
                
                int a;
                cin >> a;
                
                Map[k][i].first = a;
                Map[k][i].second = tileNum;
            }
        }
    }
 
    BFS();
    
    // 경로 구하는 과정 
    int idx = last;
    while(path[idx] != 0)
    {
        trace.push_back(idx);
        idx = path[idx];
    }
    trace.push_back(1);
    
    cout << trace.size() << endl;
    for(int i = trace.size()-1; i >= 0; i--)
    {
        cout << trace[i] << " ";
    }
        
    return 0;
}
cs
저작자표시

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

[백준 16933] 벽 부수고 이동하기3 (BFS) (C/C+)  (0) 2021.01.19
[백준 17471] 게리맨더링 (DFS) (C/C+) (★)  (0) 2021.01.17
[백준 1939] 중량제한 (BFS, BinarySearch) (C/C++) (★★★)  (0) 2020.05.24
[백준 4991] 로봇 청소기 (BFS, Bitmask) (C/C++) (★★★)  (0) 2020.05.21
[백준 2638] 치즈 (BFS) (C/C++) (★★★)  (0) 2020.04.07
#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
 
int N, M;
vector<pair<int, long long>> v[10010];
int start, arrive;
long long Max;
long long MaxCost;
 
bool BFS(int limit)
{
    queue<int> q;
    int visited[10010] = {0};
    
    q.push(start);
    visited[start] = 1;
    
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        
        if(x == arrive)
        {
            return true;
        }
        
        for(int i = 0; i < v[x].size(); i++)
        {
            if(visited[v[x][i].first] == 0 && v[x][i].second >= limit)
            {
                visited[v[x][i].first] = 1;
                q.push(v[x][i].first);
            }
        }
    }
    
    return false;
}
 
int main(void)
{
//    freopen("B1939_input.txt", "r", stdin);
    
    cin >> N >> M;
    
    for(int i = 1; i <= M; i++)
    {
        int from, to;
        long long cost;
        cin >> from >> to >> cost;
        
        v[from].push_back({to, cost});
        v[to].push_back({from, cost});
        
        MaxCost = max(MaxCost, cost);
    }
    
    cin >> start >> arrive;
    
    long long left = 1;
    long long right = MaxCost;
    
    while(left <= right)
    {
        long long mid = (left + right) / 2;
        
        if(BFS(mid))
        {
            left = mid+1;    
            Max = mid;
        }
        else
        {
            right = mid-1;
        }
    }
    
    cout << Max << endl;
        
    return 0;
}
cs
저작자표시

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

[백준 17471] 게리맨더링 (DFS) (C/C+) (★)  (0) 2021.01.17
[백준 5213] 과외맨 (BFS) (C/C++) (★★)  (0) 2020.05.26
[백준 4991] 로봇 청소기 (BFS, Bitmask) (C/C++) (★★★)  (0) 2020.05.21
[백준 2638] 치즈 (BFS) (C/C++) (★★★)  (0) 2020.04.07
[백준 2589] 보물섬 (BFS) (C/C++)  (0) 2020.04.07
#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

+ Recent posts

티스토리툴바