#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

1.

#include <stdio.h>
#include <iostream>
using namespace std;
 
int city[15][15];
int visited[15];
int N;
int Min = 99999999;
 
int check()
{
    for(int i = 1; i < N; i++)
    {
        if(visited[i] == 0)
        {
            return 0;
        }
    }
    
    return 1;
}
 
void DFS(int sum, int cur)
{
    // 1번 ~ N-1번 도시를 모두 방문한 경우
    if(check() == 1)
    {
        // 0번 마을까지의 경로가 존재한다면 
        if(city[cur][0] != 0)
        {
            sum += city[cur][0];
        
            if(sum < Min)
            {
                Min = sum;
            }    
        }
        
        return;
    }
    
    for(int i = 1; i < N; i++)
    {
        if(city[cur][i] != 0 && visited[i] == 0)
        {
            visited[i] = 1;
            DFS(sum + city[cur][i], i);
            visited[i] = 0;
        }
    }
}
 
int main(void)
{
//    freopen("B10971_input.txt", "r", stdin);
    
    scanf("%d", &N);
    
    // 0번 ~ N-1번 도시 
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            scanf("%d", &city[i][j]);
        }
    }
    
    // 0 →1 →2 →3 →4 →0  시작점이 0인 최소비용 루트가 있다고 가정해보자. 이 때 'A원'의 비용이 들었다면, 
    // 2 →3 →4 →0 →1 →2  시작점이 2인 최소비용 루트는 시작점과 관계없이 'A원'의 비용이 든다. 
    DFS(0, 0);    
    
    cout << Min;
    
    return 0;
}
 cs

 

2.

#include <stdio.h>
#include <iostream>
using namespace std;
 
int city[15][15];
int visited[15];
int N;
int Min = 99999999;
 
int check()
{
    for(int i = 1; i <= N; i++)
    {
        if(visited[i] == 0)
        {
            return 0;
        }
    }
    
    return 1;
}
 
void DFS(int sum, int start, int arrive)
{
    if(check() == 1)
    {
        // 출발점으로 돌아올때 0이 아닌 조건을 추가해주는것이 중요 
        if(city[start][arrive] != 0)
        {
            sum += city[start][arrive];
        
            if(sum < Min)
            {
                Min = sum;
            }    
        }
        
        return;
    }
    
    for(int i = 1; i <= N; i++)
    {
        if(city[start][i] != 0 && visited[i] == 0)
        {
            visited[i] = 1;
            DFS(sum + city[start][i], i, arrive);
            visited[i] = 0;
        }
    }
}
 
int main(void)
{
//    freopen("B10971_input.txt", "r", stdin);
    
    scanf("%d", &N);
    
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            scanf("%d", &city[i][j]);
        }
    }
    
    for(int i = 1; i <= N; i++)
    {        
        visited[i] = 1;
        DFS(0, i, i);    
        visited[i] = 0;
    }
    
    cout << Min;
    
    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
[백준 14500] 테트로미노 (DFS) (C/C++) (★)  (0) 2019.11.19
[백준 2210] 숫자판 점프 (DFS) (C/C++)  (1) 2019.11.18
#include <stdio.h>
#include <iostream>
using namespace std;
 
int choice[5];
int same[300][300];
int N, M;
int ans;
 
int check(int num, int cnt)
{
    for(int i = 0; i < cnt; i++)
    {
        if(same[choice[i]][num] == 1)
        {
            return 0;
        }
    }
    
    return 1;
}
 
void combination(int idx, int cnt)
{
    if(cnt == 4)
    {
        ans++;
        
        return;
    }
    
    for(int i = idx; i <= N; i++)
    {
        choice[cnt] = i;
        
        // 선택한 수가 조건에 위배되지않는지 확인 
        if(check(choice[cnt], cnt) == 1)
        {
            combination(i+1, cnt+1);
        }
    }    
}
 
int main(void)
{
//    freopen("B2422_input.txt", "r", stdin);
    
    scanf("%d %d", &N, &M);
    
    for(int i = 1; i <= M; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        same[a][b] = 1;
        same[b][a] = 1;
    }
    
    combination(1, 1);
    
    printf("%d", ans);
    
    return 0;
}
cs
저작자표시

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

[백준 14888] 연산자 끼워넣기 (순열) (C/C++)  (0) 2019.11.20
[백준 14501] 퇴사 (조합) (C/C++) (★)  (0) 2019.11.20
[백준 3980] 선발 명단 (순열) (C/C++) (★)  (0) 2019.11.18
[백준 15661] 링크와 스타트 (조합) (C/C++) (★★)  (0) 2019.11.18
[백준 15686] 치킨배달 (조합) (C/C++)  (0) 2019.11.18
#include <stdio.h>
#include <iostream>
using namespace std;
 
int map[10][10];
int choice[10];
int visited[1000000];
int ans;
 
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 < 5 && y < 5)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void DFS(int x, int y, int cnt)
{    
    if(cnt == 7)
    {
        int val = choice[0]*100000 + choice[1]*10000 + choice[2]*1000 + choice[3]*100 + choice[4]*10 + choice[5]*1;
        
        if(visited[val] == 0)
        {
            visited[val] = 1;
            ans++;
        }
        
        return;
    }
    
    for(int i = 0; i < 4; i++)
    {
        int xpos = x+dx[i];
        int ypos = y+dy[i];
        
        if(safe(xpos, ypos) == 1)
        {
            choice[cnt] = map[xpos][ypos];
            DFS(xpos, ypos, cnt+1);    
        }
    }
}
 
int main(void)
{
//    freopen("B2210_input.txt", "r", stdin);
    
    for(int i = 0; i < 5; i++)
    {
        for(int j = 0; j < 5; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
    
    for(int i = 0; i < 5; i++)
    {
        for(int j = 0; j < 5; j++)
        {
            DFS(i, j, 0);
        }
    }
    
    cout << ans;
    
    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
[백준 14500] 테트로미노 (DFS) (C/C++) (★)  (0) 2019.11.19
[백준 10971] 외판원 순회2 (DFS) (C/C++) (★)  (0) 2019.11.19
#include <stdio.h>
#include <iostream>
using namespace std;
 
typedef struct node
{
    int pos[20];
}node;
 
int N;
int visited[20];
int Max;
node player[20];
 
void permutation(int sum, int cnt)
{
    if(cnt == 12)
    {
        if(sum > Max)
        {
            Max = sum;
        }
        
        return;
    }
    
    for(int i = 1; i <= 11; i++)
    {
        if(visited[i] == 0 && player[cnt].pos[i] != 0)
        {
            visited[i] = 1;
            permutation(sum + player[cnt].pos[i], cnt+1);
            visited[i] = 0;    
        }
    }
}
 
int main(void)
{
//    freopen("B3980_input.txt", "r", stdin);
    
    scanf("%d", &N);
    
    for(int T = 1; T <= N; T++)
    {
        for(int i = 1; i <= 11; i++)
        {
            for(int j = 1; j <= 11; j++)
            {
                cin >> player[i].pos[j];
            }
        }
        
        Max = 0;
        for(int i = 0; i < 20; i++)
        {
            visited[i] = 0;
        }
        
        permutation(0, 1);
        
        printf("%d\n", Max);
    }
    
    return 0;
}
cs
저작자표시

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

[백준 14501] 퇴사 (조합) (C/C++) (★)  (0) 2019.11.20
[백준 2422] 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (조합) (C/C++) (★)  (1) 2019.11.19
[백준 15661] 링크와 스타트 (조합) (C/C++) (★★)  (0) 2019.11.18
[백준 15686] 치킨배달 (조합) (C/C++)  (0) 2019.11.18
[백준 2309] 일곱 난쟁이 (조합) (C/C++)  (1) 2019.11.18
#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;
 
int map[30][30];
int N;
int Min = 9999999;
 
void combination(int start[], int visited[], int idx, int cnt, int std)
{
    if(cnt == std + 1)
    {
        int startSum = 0;
        int linkSum = 0;
        
        int link[20];
        int linkCnt = 0;
        
        for(int i = 1; i <= N; i++)
        {
            if(visited[i] == 0)
            {
                link[++linkCnt] = i;
            }
        }
        
        for(int i = 1; i < cnt; i++)
        {
            for(int j = 1; j < cnt; j++)
            {
                startSum += map[start[i]][start[j]];
            }
        }
        
        for(int i = 1; i <= linkCnt; i++)
        {
            for(int j = 1; j <= linkCnt; j++)
            {
                linkSum += map[link[i]][link[j]];
            }
        }
        
        if(abs(startSum-linkSum) < Min)
        {
            Min = abs(startSum-linkSum);
        }
        
        return;
    }
    
    for(int i = idx; i <= N; i++)
    {
        start[cnt] = i;
        visited[i] = 1;
        combination(start, visited, i+1, cnt+1, std);
        visited[i] = 0;
    }
}
 
int main(void)
{
//    freopen("B15661_input.txt", "r", stdin);
    
    scanf("%d", &N);
    
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
    
    // 팀원이 최소 1명 ~ N/2명 
    for(int i = 1; i <= N/2; i++)
    {
        int start[20] = {0};
        int visited[20] = {0};
        combination(start, visited, 1, 1, i);    
    }
    
    cout << Min;
    
    return 0;
}
cs
저작자표시

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

[백준 2422] 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (조합) (C/C++) (★)  (1) 2019.11.19
[백준 3980] 선발 명단 (순열) (C/C++) (★)  (0) 2019.11.18
[백준 15686] 치킨배달 (조합) (C/C++)  (0) 2019.11.18
[백준 2309] 일곱 난쟁이 (조합) (C/C++)  (1) 2019.11.18
[백준 2529] 부등호 (순열) (C/C++)  (0) 2019.11.18
#include <stdio.h>
#include <vector>
#include <math.h>
#include <iostream>
using namespace std;
 
int map[60][60];
int N, M;
vector<pair<int, int>> chicken;
vector<pair<int, int>> house;
vector<pair<int, int>> choice;
int Min = 9999999;
 
int check(pair<int, int> house, vector<pair<int, int>> choice)
{
    int dMin = 9999999;
    
    for(int i = 0; i < choice.size(); i++)
    {
        int d = abs(house.first - choice[i].first) + abs(house.second - choice[i].second);
        
        if(d < dMin)
        {
            dMin = d;
        }
    }
    
    return dMin;
}
 
void combination(int idx, int cnt)
{
    if(cnt == M)
    {
        int sum = 0;
        
        for(int i = 0; i < house.size(); i++)
        {
            sum += check(house[i], choice);    
        }
        
        if(sum < Min)
        {
            Min = sum;
        }
        
        return;
    }
    
    for(int i = idx; i < chicken.size(); i++)
    {
        choice.push_back({chicken[i].first, chicken[i].second});
        combination(i+1, cnt+1);
        choice.pop_back();
    }
}
 
int main(void)
{
//    freopen("B15686_input.txt", "r", stdin);
    
    scanf("%d %d", &N, &M);
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            cin >> map[i][j];
            
            if(map[i][j] == 1)
            {
                house.push_back({i, j});
            }
            else if(map[i][j] == 2)
            {
                chicken.push_back({i, j});
            }
        }
    }
    
    combination(0, 0);
    
    printf("%d", Min);
    
    return 0;
}
cs
저작자표시

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

[백준 3980] 선발 명단 (순열) (C/C++) (★)  (0) 2019.11.18
[백준 15661] 링크와 스타트 (조합) (C/C++) (★★)  (0) 2019.11.18
[백준 2309] 일곱 난쟁이 (조합) (C/C++)  (1) 2019.11.18
[백준 2529] 부등호 (순열) (C/C++)  (0) 2019.11.18
[백준 15666] N과 M(12) (중복조합) (C/C++)  (0) 2019.11.18
#include <stdio.h>
 
int height[7];
int input[9];
int flag;
 
void combination(int sum, int cnt, int idx)
{        
    if(cnt == 7)
    {        
        if(sum == 100)
        {
            flag = 1;
            return;
        }
        else
        {
            return;
        }
    }
    
    for(int i = idx; i < 9; i++)
    {
        height[cnt] = input[i];
        combination(sum + height[cnt], cnt+1, i+1);
        if(flag == 1)
        {
            return;
        }
    }
}
 
int main(void)
{
//    freopen("B2309_input.txt", "r", stdin);
    
    for(int i = 0; i < 9; i++)
    {
        scanf("%d", &input[i]);
    }
    
    combination(0, 0, 0);
    
    // 버블 정렬 -> 오름차순 출력을 위해 
    for(int i = 6; i > 0; i--)
    {
        for(int j = 0; j < i; j++)
        {
            if(height[j] > height[j+1])
            {
                int temp = height[j];
                height[j] = height[j+1];
                height[j+1] = temp;
            }
        }
    }
    
    for(int i = 0; i < 7; i++)
    {
        printf("%d\n", height[i]);
    }
    
    return 0;
}
cs
저작자표시

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

[백준 15661] 링크와 스타트 (조합) (C/C++) (★★)  (0) 2019.11.18
[백준 15686] 치킨배달 (조합) (C/C++)  (0) 2019.11.18
[백준 2529] 부등호 (순열) (C/C++)  (0) 2019.11.18
[백준 15666] N과 M(12) (중복조합) (C/C++)  (0) 2019.11.18
[백준 15665] N과 M(11) (중복순열) (C/C++)  (0) 2019.11.18

+ Recent posts

티스토리툴바