#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 <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 <vector>
#include <map>
using namespace std;
 
vector<int> graph[55];
int N;
int rootNode;
int delNode;
int leafCnt;
 
void find_leaf(int node)
{
    if(graph[node].size() == 0)
    {
        leafCnt++;
    }
    
    for(int i = 0; i < graph[node].size(); i++)
    {
        // 현재노드의 자식이 삭제할 노드이고, 
        if(graph[node][i] == delNode)
        {
            // 현재노드의 자식이 1개 밖에 없으면, 현재 노드의 자식을 삭제할 경우 그 현재 노드가 리프노드가 됨 
            if(graph[node].size() == 1)
            {
                leafCnt++;    
            }
            
            continue;
        }
        
        find_leaf(graph[node][i]);
    }
}
 
int main(void)
{
//    freopen("B1068_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int to = 0; to < N; to++)
    {
        int from;
        cin >> from;
        
        if(from == -1)
        {
            rootNode = to;
            
            continue;
        }
        else
        {
            graph[from].push_back(to);    
        }
    }
    
    cin >> delNode;
    
    if(delNode == rootNode)
    {
        cout << "0";
    }
    else
    {
        find_leaf(rootNode);
        cout << leafCnt;    
    }
    
    return 0;
}
cs
저작자표시

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

[백준 17779] 게리맨더링2 (DFS) (C/C+) (★)  (0) 2021.01.17
[백준 1325] 효율적인 해킹 (DFS) (C/C++) (★)  (0) 2020.05.24
[백준 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 <algorithm>
#include <string>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
 
int T;
int N;
int map[100010];
int visited[100010]; // 0: 아직 시도안함 , -1: 팀을 찾음, 나머지: 팀을 못찾음 
bool flag;
vector<int> check; // 팀원 저장용
 
int stopMember;
 
void DFS(int start, int cnt)
{
    if(flag == true)
    {
        return;
    }
        
    if(visited[map[start]] == 0)
    {
        // 팀이 되는 경우에, 사람을 체크하기 위해서 
        check.push_back(map[start]);
        
        visited[map[start]] = cnt;
        DFS(map[start], cnt);
    }
    // 팀이 되는 경우 
    else if(visited[map[start]] == cnt)
    {
        // 처음과 끝이되는 멤버 체크 
        stopMember = map[start];
 
        flag = true;
        
        return;
    }
}
 
int main(void)
{
//    freopen("B9466_input.txt", "r", stdin);
    
    cin >> T;
    
    for(int k = 1; k <= T; k++)
    {
        for(int i = 0; i <= 100000; i++)
        {
            map[i] = 0;
            visited[i] = 0;
        }
        
        cin >> N;
        
        for(int a = 1; a <= N; a++)
        {
            int b;
            cin >> b;
            
            map[a] = b;
        }
        
        int cnt = 1;
        for(int i = 1; i <= N; i++)
        {
            check.clear();
            flag = false;
            
            // 혼자하고 싶어하는 경우 
            if(i == map[i])
            {
                visited[i] = -1;
                continue;
            }
            
            // 팀으로 할 가능성이 있는 경우 
            if(visited[i] == 0)
            {
                visited[i] = cnt;
                check.push_back(i);
                DFS(i, cnt);
                
                if(flag == true)
                {                    
                    // stopMember의 인덱스 찾기
                    int stopMemberIdx; 
                    for(int j = 0; j < check.size(); j++)
                    {
                        if(check[j] == stopMember)
                        {
                            stopMemberIdx = j;    
                            break;                
                        }
                    }    
                    
                    // stopMember부터 팀이 된 사람 -1 체크
                    for(int j = stopMemberIdx; j < check.size(); j++)
                    {
                        visited[check[j]] = -1;
                    }    
                } 
                
                cnt++;
            }
        }
        
        int ans = 0;
        for(int i = 1; i <= N; i++)
        {
            if(visited[i] != -1)
            {
                ans++;
            }
        }
        
        cout << ans << endl;
    }
    
    return 0;
}
cs
저작자표시

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

[백준 1325] 효율적인 해킹 (DFS) (C/C++) (★)  (0) 2020.05.24
[백준 1068] 트리 (DFS, Tree) (C/C++) (★)  (0) 2020.02.16
[백준 2667] 단지번호 붙이기 (DFS) (C/C++)  (0) 2020.01.26
[백준 10451] 순열 사이클 (DFS) (C/C++)  (0) 2020.01.26
[백준 13023] ABCDE (DFS) (C/C++)  (0) 2019.12.08
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int N;
int map[30][30];
int visited[30][30];
int houseNum;
int Size;
vector<int> complex;
 
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 < N && y < N)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void DFS(int x, int y, int color)
{
    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] == 1 && visited[xpos][ypos] == 0)
        {
            visited[xpos][ypos] = color;
            DFS(xpos, ypos, color);
            Size++;
        }
    }
}
 
int main(void)
{
    // freopen("B2667_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            scanf("%1d", &map[i][j]);        
        }
    }
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(map[i][j] == 1 && visited[i][j] == 0)
            {
                Size = 1;
                houseNum++;
                visited[i][j] = houseNum;
                DFS(i, j, houseNum);
                complex.push_back(Size);
            }
        }
    }
    
    cout << houseNum << endl;
    
    sort(complex.begin(), complex.end());
    for(int i = 0; i < complex.size(); i++)
    {
        cout << complex[i] << endl;
    }
        
    return 0;
}
cs
저작자표시

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

[백준 1068] 트리 (DFS, Tree) (C/C++) (★)  (0) 2020.02.16
[백준 9466] 텀 프로젝트 (DFS) (C/C++) (★★★)  (0) 2020.01.26
[백준 10451] 순열 사이클 (DFS) (C/C++)  (0) 2020.01.26
[백준 13023] ABCDE (DFS) (C/C++)  (0) 2019.12.08
[백준 14500] 테트로미노 (DFS) (C/C++) (★)  (0) 2019.11.19
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <map>
#include <vector>
using namespace std;
 
int T;
int N;
vector<int> graph[1010];
int visited[1010];
 
void DFS(int start)
{
    visited[start] = 1;
    
    for(int i = 0; i < graph[start].size(); i++)
    {
        if(visited[graph[start][i]] == 0)
        {
            DFS(graph[start][i]);
        }
    }    
}
 
int main(void)
{
//    freopen("B10451_input.txt", "r", stdin);
    
    cin >> T;
    
    for(int k = 1; k <= T; k++)
    {
        for(int i = 1; i <= 1000; i++)
        {
            graph[i].clear();
        }
        memset(visited, 0, sizeof(visited));
        
        cin >> N;
        
        for(int a = 1; a <= N; a++)
        {
            int b;
            cin >> b;
            
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
        
        int cnt = 0;
        for(int i = 1; i <= N; i++)
        {
            if(visited[i] == 0)
            {
                DFS(i);
                
                cnt++;
            }
        }
        
        cout << cnt << endl;
    }
    
    return 0;
}
cs
저작자표시

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

[백준 9466] 텀 프로젝트 (DFS) (C/C++) (★★★)  (0) 2020.01.26
[백준 2667] 단지번호 붙이기 (DFS) (C/C++)  (0) 2020.01.26
[백준 13023] ABCDE (DFS) (C/C++)  (0) 2019.12.08
[백준 14500] 테트로미노 (DFS) (C/C++) (★)  (0) 2019.11.19
[백준 10971] 외판원 순회2 (DFS) (C/C++) (★)  (0) 2019.11.19
#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
 
int peopleNum, relation;
bool flag = false;
 
vector<int> v[2010];
int visited[2010];
 
void DFS(int start, int cnt)
{
    if(cnt == 4)
    {
        flag = true;
        return;
    }
    
    for(int i = 0; i < v[start].size(); i++)
    {
        if(visited[v[start][i]] == 0)
        {
            visited[v[start][i]] = 1;
            DFS(v[start][i], cnt+1);
            visited[v[start][i]] = 0;
            
            if(flag == true)
            {
                return;
            }
        }
    }
}
 
int main(void)
{
//    freopen("B13023_input.txt", "r", stdin);
    
    cin >> peopleNum >> relation;
    
    for(int i = 1; i <= relation; i++)
    {
        int a, b;
        cin >> a >> b;
        
        v[a].push_back(b);
        v[b].push_back(a);
    }
    
    for(int i = 0; i < peopleNum; i++)
    {
        memset(visited, 0, sizeof(visited));
        
        visited[i] = 1;
        DFS(i, 0);
        visited[i] = 0;
        
        if(flag == true)
        {
            cout << "1" << endl;
            break;
        }
    }
    
    if(flag == false)
    {
        cout << "0" << endl;
    }
    
    return 0;
}
cs
저작자표시

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

[백준 2667] 단지번호 붙이기 (DFS) (C/C++)  (0) 2020.01.26
[백준 10451] 순열 사이클 (DFS) (C/C++)  (0) 2020.01.26
[백준 14500] 테트로미노 (DFS) (C/C++) (★)  (0) 2019.11.19
[백준 10971] 외판원 순회2 (DFS) (C/C++) (★)  (0) 2019.11.19
[백준 2210] 숫자판 점프 (DFS) (C/C++)  (1) 2019.11.18
#include <stdio.h>
#include <iostream>
using namespace std;
 
int map[500][500];
int visited[500][500];
int Max;
int N, M;
 
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 < N && y < M)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void check(int i, int j)
{
    if(safe(i+1, j+2) == 1)
    {
        int val = map[i][j] + map[i][j+1] + map[i][j+2] + map[i+1][j+1]; // ㅜ 
        
        if(val > Max)
        {
            Max = val;
        }    
    } 
    
    if(safe(i-1, j+2) == 1)
    {
        int val = map[i][j] + map[i][j+1] + map[i][j+2] + map[i-1][j+1]; // ㅗ 
        
        if(val > Max)
        {
            Max = val;
        }    
    } 
    
    if(safe(i+2, j-1) == 1)
    {
        int val = map[i][j] + map[i+1][j] + map[i+2][j] + map[i+1][j-1]; // ㅓ 
        
        if(val > Max)
        {
            Max = val;
        }    
    }
    
    if(safe(i+2, j+1) == 1)
    {
        int val = map[i][j] + map[i+1][j] + map[i+2][j] + map[i+1][j+1]; // ㅏ 
        
        if(val > Max)
        {
            Max = val;
        }    
    }
}
 
void DFS(int sum, int x, int y, int cnt)
{
    if(cnt == 4)
    {
        if(sum > Max)
        {
            Max = sum;
        }
        
        return;
    }
    
    for(int i = 0; i < 4; i++)
    {
        int xpos = x+dx[i];
        int ypos = y+dy[i];
        
        if(safe(xpos, ypos) == 1 && visited[xpos][ypos] == 0)
        {
            visited[xpos][ypos] = 1;
            DFS(sum + map[xpos][ypos], xpos, ypos, cnt+1);
            visited[xpos][ypos] = 0;
        }
    }
}
 
int main(void)
{
//    freopen("B14500_input.txt", "r", stdin);
    
    scanf("%d %d", &N, &M);
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            visited[i][j] = 1;
            DFS(map[i][j], i, j, 1);
            check(i, j);
            visited[i][j] = 0;
        }
    }
        
    printf("%d", Max);
    
    return 0;
}
 cs
저작자표시

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

[백준 2667] 단지번호 붙이기 (DFS) (C/C++)  (0) 2020.01.26
[백준 10451] 순열 사이클 (DFS) (C/C++)  (0) 2020.01.26
[백준 13023] ABCDE (DFS) (C/C++)  (0) 2019.12.08
[백준 10971] 외판원 순회2 (DFS) (C/C++) (★)  (0) 2019.11.19
[백준 2210] 숫자판 점프 (DFS) (C/C++)  (1) 2019.11.18

+ Recent posts

티스토리툴바