BFS

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int map[110][110];
int people;
int relation;
int s, e;
int ans;
 
queue<int> q;
int visited[110];
 
void BFS()
{
    visited[s] = 1;
    q.push(s);
    
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        
        if(now == e)
        {
            return;
        }
        
        for(int i = 1; i <= people; i++)
        {
            if(map[now][i] == 1 && visited[i] == 0)
            {
                visited[i] = visited[now] + 1;
                q.push(i);
            }
        }
    }
}
 
int main(void)
{
//    freopen("B2644_input.txt", "r", stdin);
 
    cin >> people;
    cin >> s >> e;
    cin >> relation;
    
    for(int i = 1; i <= relation; i++)
    {
        int a, b;
        cin >> a >> b;
        
        map[a][b] = 1;
        map[b][a] = 1;
    }
    
    BFS();
    
    if(visited[e] == 0)
    {
        cout << -1;
    }
    else
    {
        cout << visited[e]-1;    
    }
 
    return 0;
}
 cs

 

Floyd-Warshall

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int map[110][110];
int visited[110][110];
int people;
int relation;
int s, e;
int ans;
 
void floyd()
{
    for(int k = 1; k <= people; k++)
    {
        for(int i = 1; i <= people; i++)
        {
            for(int j = 1; j <= people; j++)
            {
                if(i == j)
                {
                    continue;
                }
                
                if(map[i][k] != 0 && map[k][j] != 0 && visited[i][j] == 0)
                {
                    visited[i][j] = 1;
                    visited[j][i] = 1;
                    
                    map[i][j] = map[i][k] + map[k][j];
                    map[j][i] = map[i][k] + map[k][j];
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B2644_input.txt", "r", stdin);
 
    cin >> people;
    cin >> s >> e;
    cin >> relation;
    
    for(int i = 1; i <= relation; i++)
    {
        int a, b;
        cin >> a >> b;
        
        map[a][b] = 1;
        map[b][a] = 1;
    }
    
    floyd();
    
    if(map[s][e] == 0)
    {
        cout << -1;
    }
    else
    {
        cout << map[s][e];    
    }
 
    return 0;
}
 cs
저작자표시

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

[백준 1507] 궁금한 민호 (Floyd-Warshall) (C/C++) (★★)  (0) 2020.02.08
[백준 5567] 결혼식 (Floyd-Warshall) (C/C++)  (0) 2020.02.07
[백준 11404] 플로이드 (Floyd-Warshall) (C/C++)  (0) 2020.02.07
[백준 1613] 역사 (Floyd-Warshall) (C/C++) (★)  (0) 2019.11.20
[백준 11403] 경로찾기 (Floyd-Warshall) (C/C++)  (0) 2019.11.20
#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int map[110][110];
int N;
int safeArea = 1;
int minArea = 99999;
int maxArea = -99999;
 
queue<pair<int, int>> q;
int visited[110][110];
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
void init()
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            visited[i][j] = 0;
        }
    }
}
 
int safe(int x, int y)
{
    if(x >= 0 && x < N && y >= 0 && y < N)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS(int x, int y, int rain)
{
    visited[x][y] = 1;
    q.push({x, y});
    
    while(!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        
        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 && map[xpos][ypos] > rain)
            {
                visited[xpos][ypos] = 1;
                q.push({xpos, ypos});
            }
        }
    }
}
 
int main(void)
{
//    freopen("B2468_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            cin >> map[i][j];
            
            // 영역의 최소, 최대 높이 구하기 
            if(maxArea < map[i][j])
            {
                maxArea = map[i][j];
            }
            
            if(minArea > map[i][j])
            {
                minArea = map[i][j];
            }
        }
    }
    
    // 영역의 최소, 최대 높이만큼만 비를 계산하면 됨 
    for(int k = minArea; k <= maxArea; k++)
    {
        int cnt = 0;
        init();
        
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < N; j++)
            {
                // 비에 따른 안전영역 계산     
                if(visited[i][j] == 0 && map[i][j] > k)
                {
                    BFS(i, j, k);
                    cnt++;
                }
            }
        }
        
        if(safeArea < cnt)
        {
            safeArea = cnt;
        }
    }
    
    cout << safeArea;
    
    return 0;
}
cs
저작자표시

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

[백준 2206] 벽 부수고 이동하기 (BFS) (C/C++)  (0) 2019.12.04
[백준 11724] 연결요소의 개수 (BFS) (C/C++)  (0) 2019.12.04
[백준 9177] 단어 섞기 (DFS/BFS) (C/C++) (★★)  (0) 2019.12.04
[백준 7562] 나이트의 이동 (BFS) (C/C++)  (0) 2019.12.03
[백준 2251] 물통 (BFS) (C/C++)  (0) 2019.12.02

DFS

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
string a, b, c;
int T;
bool beforeFlag = true;
bool afterFlag = false;
    
void init()
{
    // 소문자 & 대문자 counting 
    int abCnt[52] = {0};
    int cCnt[52] = {0};
    
    for(int i = 0; i < a.size(); i++)
    {
        if('A' <= a[i] && a[i] <= 'Z')
        {
            abCnt[a[i]-'A'+26]++;
        }
        else
        {
            abCnt[a[i]-'a']++;   
        }
    }    
    
    for(int i = 0; i < b.size(); i++)
    {
        if('A' <= b[i] && b[i] <= 'Z')
        {
            abCnt[b[i]-'A'+26]++;
        }
        else
        {
            abCnt[b[i]-'a']++;    
        }
    }    
    
    for(int i = 0; i < c.size(); i++)
    {
        if('A' <= c[i] && c[i] <= 'Z')
        {
            cCnt[c[i]-'A'+26]++;
        }
        else
        {
            cCnt[c[i]-'a']++;
        }
    }    
    
    for(int i = 0; i < 52; i++)
    {
        if(abCnt[i] != cCnt[i])
        {
            beforeFlag = false;
            return;
        }
    }
}
 
void backtracking(int aIdx, int bIdx, int cIdx, string result)
{
    if(afterFlag == true)
    {
        return;
    }
    
    if(result == c)
    {
        afterFlag = true;
        return;
    }
    
    if(a[aIdx] == c[cIdx] && aIdx < a.size())
    {
        backtracking(aIdx+1, bIdx, cIdx+1, result+a[aIdx]);    
    }
    
    if(b[bIdx] == c[cIdx] && bIdx < b.size())
    {
        backtracking(aIdx, bIdx+1, cIdx+1, result+b[bIdx]);    
    }
} 
 
int main(void)
{
//    freopen("B9177_input.txt", "r", stdin);
    
    cin >> T;
 
    for(int n = 1; n <= T; n++)
    {
        cin >> a >> b >> c;
        
        beforeFlag = true;
        afterFlag = false;
        
        init();
        
        // 소문자 & 대문자 갯수로 미리 판별 
        if(beforeFlag == false)
        {
            printf("Data set %d: no\n", n);
            continue;
        }
        
        backtracking(0, 0, 0, "");
        
        if(afterFlag == true)
        {
            printf("Data set %d: yes\n", n);
        }
        else
        {
            printf("Data set %d: no\n", n);
        }
    }
    
    return 0;
}
 cs

 

BFS

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
typedef struct node
{
    int aIdx;
    int bIdx;
    int cIdx;
}node;
 
string a, b, c;
int T;
bool flag = false;
 
queue<node> q;
int visited[210][210];
 
void init()
{
    for(int i = 0; i < 210; i++)
    {
        for(int j = 0; j < 210; j++)
        {
            visited[i][j] = 0;
        }
    }
}
 
void BFS()
{
    visited[0][0] = 1;
    q.push({0, 0, 0});
    
    while(!q.empty())
    {
        int aIdx = q.front().aIdx;
        int bIdx = q.front().bIdx;
        int cIdx = q.front().cIdx;
        q.pop();
        
        if(cIdx == c.size())
        {
            flag = true;
            return;
        }
        
        if(visited[aIdx+1][bIdx] == 0 && a[aIdx] == c[cIdx])
        {
            visited[aIdx+1][bIdx] = 1;
            q.push({aIdx+1, bIdx, cIdx+1});
        }
        
        if(visited[aIdx][bIdx+1] == 0 && b[bIdx] == c[cIdx])
        {
            visited[aIdx][bIdx+1] = 1;
            q.push({aIdx, bIdx+1, cIdx+1});
        }
    }
} 
 
int main(void)
{
//    freopen("B9177_input.txt", "r", stdin);
    
    cin >> T;
 
    for(int n = 1; n <= T; n++)
    {
        cin >> a >> b >> c;
        
        flag = false;
        
        init();
        
        BFS();
        
        if(flag == true)
        {
            printf("Data set %d: yes\n", n);
        }
        else
        {
            printf("Data set %d: no\n", n);
        }
    }
    
    return 0;
}
 cs
저작자표시

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

[백준 11724] 연결요소의 개수 (BFS) (C/C++)  (0) 2019.12.04
[백준 2468] 안전영역 (BFS) (C/C++)  (0) 2019.12.04
[백준 7562] 나이트의 이동 (BFS) (C/C++)  (0) 2019.12.03
[백준 2251] 물통 (BFS) (C/C++)  (0) 2019.12.02
[백준 5014] 스타트 링크 (BFS) (C/C++)  (0) 2019.12.02
#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
int map[310][310];
int T;
int len;
int startX, startY, endX, endY;
 
queue<pair<int, int>> q;
int visited[310][310];
 
int dx[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
 
void init()
{
    for(int i = 0; i < len; i++)
    {
        for(int j = 0; j < len; j++)
        {
            visited[i][j] = 0;
        }
    }
}
 
int safe(int x, int y)
{
    if(x >= 0 && x < len && y >= 0 && y < len)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS()
{
    visited[startX][startY] = 1;
    q.push({startX, startY});
    
    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 8; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && visited[xpos][ypos] == 0)
            {
                visited[xpos][ypos] = visited[x][y] + 1;
                q.push({xpos, ypos});
            }
        }
    }
}
 
int main(void)
{
//    freopen("B7562_input.txt", "r", stdin);
    
    scanf("%d", &T);
    
    for(int n = 1; n <= T; n++)
    {            
        cin >> len;
        cin >> startX >> startY >> endX >> endY;
        
        BFS();
        
        cout << visited[endX][endY]-1 << endl;
        
        init();
    }
        
    return 0;
}
cs
저작자표시

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

[백준 2468] 안전영역 (BFS) (C/C++)  (0) 2019.12.04
[백준 9177] 단어 섞기 (DFS/BFS) (C/C++) (★★)  (0) 2019.12.04
[백준 2251] 물통 (BFS) (C/C++)  (0) 2019.12.02
[백준 5014] 스타트 링크 (BFS) (C/C++)  (0) 2019.12.02
[백준 1697] 숨바꼭질 (BFS) (C/C++)  (0) 2019.12.02
#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
int A, B, C;
int visited[201][201][201];
int check[201];
 
queue<int> q;
 
void BFS(int nowA, int nowB, int nowC)
{
    visited[nowA][nowB][nowC] = 1;
    q.push(nowA);
    q.push(nowB);
    q.push(nowC);
    
    // C의 용량 체크 
    check[nowC] = 1;
    
    while(!q.empty())
    {
        nowA = q.front();
        q.pop();
        nowB = q.front();
        q.pop();
        nowC = q.front();
        q.pop();
        
        for(int i = 1; i <= 6; i++)
        {
            int newA = nowA;
            int newB = nowB;
            int newC = nowC;
            
            // A->B
            if(i == 1)
            {
                if(nowA + nowB > B)
                {
                    newA = nowA + nowB - B;
                    newB = B;
                }
                else
                {
                    newB = nowA + nowB;
                    newA = 0;
                }
            }
            // B->A
            else if(i == 2)
            {
                if(nowB + nowA > A)
                {
                    newB = nowB + nowA - A;
                    newA = A;
                }
                else
                {
                    newA = nowB + nowA;
                    newB = 0;
                }
            }
            // A->C
            else if(i == 3)
            {
                if(nowA + nowC > C)
                {
                    newA = nowA + nowC - C;
                    newC = C;
                }
                else
                {
                    newC = nowA + nowC;
                    newA = 0;
                }
            }
            // C->A
            else if(i == 4)
            {
                if(nowC + nowA > A)
                {
                    newC = nowC + nowA - A;
                    newA = A;
                }
                else
                {
                    newA = nowC + nowA;
                    newC = 0;
                }
            }
            // B->C
            else if(i == 5)
            {
                if(nowB + nowC > C)
                {
                    newB = nowB + nowC - C;
                    newC = C;
                }
                else
                {
                    newC = nowB + nowC;
                    newB = 0;
                }
            }
            // C->B
            else if(i == 6)
            {
                if(nowC + nowB > B)
                {
                    newC = nowC + nowB - B;
                    newB = B;
                }
                else
                {
                    newB = nowC + nowB;
                    newC = 0;
                }
            }
            
            if(visited[newA][newB][newC] == 0)
            {
                visited[newA][newB][newC] = 1;
                q.push(newA);
                q.push(newB);
                q.push(newC);
                
                if(newA == 0 && check[newC] == 0)
                {
                    check[newC] = 1;
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B2251_input.txt", "r", stdin);
    
    cin >> A >> B >> C;
    
    BFS(0, 0, C);
    
    for(int i = 0; i <= 200; i++)
    {
        if(check[i] == 1)
        {
            cout << i << " ";
        }
    }
     
    return 0;
}
cs
저작자표시

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

[백준 2468] 안전영역 (BFS) (C/C++)  (0) 2019.12.04
[백준 9177] 단어 섞기 (DFS/BFS) (C/C++) (★★)  (0) 2019.12.04
[백준 7562] 나이트의 이동 (BFS) (C/C++)  (0) 2019.12.03
[백준 5014] 스타트 링크 (BFS) (C/C++)  (0) 2019.12.02
[백준 1697] 숨바꼭질 (BFS) (C/C++)  (0) 2019.12.02
#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
int total, start, arrive, up, down;
int visited[1000010];
queue<int> q;
 
void BFS()
{
    visited[start] = 1;
    q.push(start);
    
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        
        for(int i = 1; i <= 2; i++)
        {
            int xpos;
            // up
            if(i == 1)
            {
                xpos = x + up;
            }
            // down
            else if(i == 2)
            {
                xpos = x - down;
            }
            
            if(xpos >= 1 && xpos <= total && visited[xpos] == 0)
            {
                visited[xpos] = visited[x] + 1;
                q.push(xpos);
            }
            
            if(xpos == arrive)
            {
                return;
            }
        }
    }
}
 
int main(void)
{
//    freopen("B5014_input.txt", "r", stdin);
    
    cin >> total >> start >> arrive >> up >> down;
    
    BFS();
    
    if(visited[arrive] == 0)
    {
        cout << "use the stairs";
    }
    else
    {
        cout << visited[arrive]-1;
    }
    
    return 0;
}
cs
저작자표시

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

[백준 2468] 안전영역 (BFS) (C/C++)  (0) 2019.12.04
[백준 9177] 단어 섞기 (DFS/BFS) (C/C++) (★★)  (0) 2019.12.04
[백준 7562] 나이트의 이동 (BFS) (C/C++)  (0) 2019.12.03
[백준 2251] 물통 (BFS) (C/C++)  (0) 2019.12.02
[백준 1697] 숨바꼭질 (BFS) (C/C++)  (0) 2019.12.02
#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
int start, arrive;
int visited[100010];
 
queue<int> q;
 
void BFS()
{
    visited[start] = 1;
    q.push(start);
    
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        
        for(int i = 1; i <= 3; i++)
        {
            int xpos;
            
            if(i == 1)
            {
                xpos = x - 1;    
            }
            else if(i == 2)
            {
                xpos = x + 1;
            }
            else if(i == 3)
            {
                xpos = x * 2;
            }
            
            if(xpos >= 0 && xpos <= 100000 && visited[xpos] == 0)
            {
                visited[xpos] = visited[x] + 1;
                q.push(xpos);
            }
            
            if(xpos == arrive)
            {
                return;
            }
        }
    }
}
 
int main(void)
{
//    freopen("B1697_input.txt", "r", stdin);
    
    cin >> start >> arrive;
    
    BFS();
    
    cout << visited[arrive]-1;
        
    return 0;
}
 cs
저작자표시

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

[백준 2468] 안전영역 (BFS) (C/C++)  (0) 2019.12.04
[백준 9177] 단어 섞기 (DFS/BFS) (C/C++) (★★)  (0) 2019.12.04
[백준 7562] 나이트의 이동 (BFS) (C/C++)  (0) 2019.12.03
[백준 2251] 물통 (BFS) (C/C++)  (0) 2019.12.02
[백준 5014] 스타트 링크 (BFS) (C/C++)  (0) 2019.12.02
#include <stdio.h>
#include <iostream>
using namespace std;
 
int map[10][10];
int direct[10];
int N, M;
int Min = 99999999;
 
int cctv[10];
int cctvCnt;
pair<int, int> cctvPos[10];
 
int dx[4] = {-1, 1, 0, 0}; // 상하좌우
int dy[4] = {0, 0, -1, 1}; // 상하좌우 
 
void copy(int mapCopy[10][10])
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            mapCopy[i][j] = map[i][j];
        }
    }
}
 
void back_up(int mapCopy[10][10])
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            map[i][j] = mapCopy[i][j];
        }
    }
}
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < N && y < M)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
int zeroCount()
{
    int cnt = 0;
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            if(map[i][j] == 0)
            {
                cnt++;        
            }
        }
    }
    
    return cnt;
}
 
void cctv1(int x, int y, int dir)
{
    while(1)
    {
        int xpos = x+dx[dir];
        int ypos = y+dy[dir];
            
        if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
        {
            map[xpos][ypos] = 7;
            x = xpos;
            y = ypos;
        }
        else
        {
            break;
        }
    }    
} 
 
void cctv2(int x, int y, int dir)
{    
    if(dir == 0 || dir == 1) // 상하 
    {
        for(int i = 0; i < 2; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
    else if(dir == 2 || dir == 3) // 좌우 
    {
        for(int i = 2; i < 4; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
} 
 
void cctv3(int x, int y, int dir)
{
    if(dir == 0) // ㄴ모양 
    {
        int dx[2] = {-1, 0}; // 상우 
        int dy[2] = {0, 1};  // 상우
         
        for(int i = 0; i < 2; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
    else if(dir == 1) //「 모양 
    {
        int dx[2] = {0, 1};  // 우하 
        int dy[2] = {1, 0};  // 우하 
        
        for(int i = 0; i < 2; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
    else if(dir == 2) // ㄱ모양 
    {
        int dx[2] = {0, 1};  // 좌하 
        int dy[2] = {-1, 0}; // 좌하 
        
        for(int i = 0; i < 2; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
    else if(dir == 3) // 」모양 
    {
        int dx[2] = {-1, 0}; // 상좌 
        int dy[2] = {0, -1}; // 상좌 
        
        for(int i = 0; i < 2; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
} 
 
void cctv4(int x, int y, int dir)
{
    if(dir == 0) // ㅗ모양 
    {
        int dx[3] = {-1, 0, 0}; // 상좌우 
        int dy[3] = {0, -1, 1}; // 상좌우 
        
        for(int i = 0; i < 3; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
    else if(dir == 1) // ㅏ모양 
    {
        int dx[3] = {-1, 1, 0}; // 상하우 
        int dy[3] = {0, 0, 1};  // 상하우 
        
        for(int i = 0; i < 3; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
    else if(dir == 2) // ㅜ모양 
    {
        int dx[3] = {0, 0, 1};  // 좌우하 
        int dy[3] = {-1, 1, 0}; // 좌우하 
        
        for(int i = 0; i < 3; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }        
        }
    }
    else if(dir == 3) // ㅓ모양 
    {
        int dx[3] = {-1, 1, 0}; // 상하좌 
        int dy[3] = {0, 0, -1};  // 상하좌 
        
        for(int i = 0; i < 3; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
} 
 
void cctv5(int x, int y, int dir)
{
    for(int i = 0; i < 4; i++)
    {
        int tempx = x;
        int tempy = y;
        
        while(1)
        {
            int xpos = tempx+dx[i];
            int ypos = tempy+dy[i];
            
            if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
            {
                map[xpos][ypos] = 7;
                tempx = xpos;
                tempy = ypos;
            }    
            else
            {
                break;
            }
        }    
    }
}
 
void execute_cctv(int cnt)
{
    if(cctv[cnt] == 1)
    {
        cctv1(cctvPos[cnt].first, cctvPos[cnt].second, direct[cnt]);
    }
    else if(cctv[cnt] == 2)
    {
        cctv2(cctvPos[cnt].first, cctvPos[cnt].second, direct[cnt]);
    }
    else if(cctv[cnt] == 3)
    {
        cctv3(cctvPos[cnt].first, cctvPos[cnt].second, direct[cnt]);
    }
    else if(cctv[cnt] == 4)
    {
        cctv4(cctvPos[cnt].first, cctvPos[cnt].second, direct[cnt]);
    }
    else if(cctv[cnt] == 5)
    {
        cctv5(cctvPos[cnt].first, cctvPos[cnt].second, direct[cnt]);
    }
}
 
void permutation(int cnt)
{
    if(cnt == cctvCnt)
    {    
        // print
//        for(int i = 0; i < N; i++)
//        {
//            for(int j = 0; j < M; j++)
//            {
//                cout << map[i][j] << " ";
//            }
//            cout << endl;
//        }
//        cout << endl;
        
        int val = zeroCount();
        
        if(val < Min)
        {
            Min = val;
            // print
//            cout << Min << endl;
//            for(int i = 0; i < N; i++)
//            {
//                for(int j = 0; j < M; j++)
//                {
//                    cout << map[i][j] << " ";
//                }
//                cout << endl;
//            }
//            cout << endl;
        }
        
        return;
    }
    
    // 방향에 대한 중복순열 (0 ~ 4 // 0, 90, 180, 270) 
    for(int i = 0; i < 4; i++)
    { 
        int mapCopy[10][10];
        copy(mapCopy);
        
        direct[cnt] = i;
        execute_cctv(cnt);
        permutation(cnt+1);
    
        back_up(mapCopy);
    }
}
 
int main(void)
{
//    freopen("B15683_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]);
                
            if(map[i][j] != 0 && map[i][j] != 6)
            {
                cctv[cctvCnt] = map[i][j];
                cctvPos[cctvCnt].first = i;
                cctvPos[cctvCnt++].second = j;
            }
        }
    } 
    
    permutation(0);
    
    printf("%d", Min);
    
    return 0;
} 
cs
저작자표시

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

[백준 1251] 단어 나누기 (조합) (C/C++) (★)  (0) 2020.03.23
[백준 1041] 주사위 (조합) (C/C++)  (0) 2019.12.18
[백준 15684] 사다리 조작 (조합) (C/C++) (★★★)  (2) 2019.11.20
[백준 15686] 연산자 끼워넣기(2) (순열) (C/C++)  (0) 2019.11.20
[백준 16198] 에너지 모으기 (순열) (C/C++) (★★)  (0) 2019.11.20

+ Recent posts

티스토리툴바