#include <stdio.h>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int A, B;
int T;
 
void BFS()
{
    queue<pair<int, string>> q;
    int visited[10010] = {0};
 
    visited[A] = 1;
    q.push({A, ""});
    
    while(!q.empty())
    {
        int now = q.front().first;
        string com = q.front().second;
        q.pop();
        
        if(now == B)
        {
            cout << com << "\n";
            return;
        }
        
        for(int i = 1; i <= 4; i++)
        {
            // D
            if(i == 1)
            {
                int num = now * 2;
                
                if(num > 9999)
                {
                    num %= 10000;
                }
 
                if(visited[num] == 0)
                {
                    visited[num] = 1;
                    q.push({num, com+"D"});
                }
            }
            // S
            else if(i == 2)
            {
                int num = now;
                
                if(num == 0)
                {
                    num = 9999;
                }
                else
                {
                    num -= 1;    
                }
                
                if(visited[num] == 0)
                {
                    visited[num] = 1;
                    q.push({num, com+"S"});
                }
            }
            // L
            else if(i == 3)
            {
                int num = now;
                
                int a = num % 1000;
                int b = num / 1000;
                
                num = a*10 + b;
 
                if(visited[num] == 0)
                {
                    visited[num] = 1;
                    q.push({num, com+"L"});
                }
            }
            // R
            else if(i == 4)
            {
                int num = now;
                
                int a = num / 10;
                int b = num % 10;
                
                num = a + b*1000;
 
                if(visited[num] == 0)
                {
                    visited[num] = 1;
                    q.push({num, com+"R"});
                }
            }
        }
    }
}
    
int main(void)
{
//    freopen("B9019_input.txt", "r", stdin);
    
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    
    cin >> T;
    
    for(int n = 1; n <= T; n++)
    {
        cin >> A >> B;
        
        BFS();
    }    
    
    return 0;
}
cs
저작자표시 (새창열림)

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

[백준 1194] 달이 차오른다, 가자. (BFS, Bitmask) (C/C++) (★★★)  (0) 2019.12.11
[백준 3197] 백조의 호수 (BFS) (C/C++) (★★★)  (0) 2019.12.09
[백준 11559] Puyo Puyo (BFS) (C/C++) (★)  (0) 2019.12.08
[백준 16234] 인구이동 (BFS) (C/C++) (★★)  (0) 2019.12.07
[백준 2573] 빙산 (BFS) (C/C++) (★)  (0) 2019.12.06
#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>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
 
char map[12][6];
int ans;
bool bombFlag = false;
 
queue<pair<int, int>> q;
int visited[12][6];
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
void init()
{
    for(int i = 0; i < 12; i++)
    {
        for(int j = 0; j < 6; j++)
        {
            visited[i][j] = 0;
        }
    }
}
 
int safe(int x, int y)
{
    if(x >= 0 && x < 12 && y >= 0 && y < 6)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void down()
{
    for(int j = 0; j < 6; j++)
    {
        for(int i = 11; i >= 0; i--)
        {
            if(map[i][j] != '.')
            {
                for(int k = 11; k > i; k--)
                {
                    if(map[k][j] == '.')
                    {
                        map[k][j] = map[i][j];
                        map[i][j] = '.';
                        break;
                    }
                }
            }
        }
    }
}
 
/*
void down()
{    
    // ↓이기때문에 열을 기준으로 
    for(int j = 0; j < 6; j++)
    {
        // 아래에서부터 위로 
        for(int i = 11; i >= 0; i--)
        {
            if(map[i][j] != '.')
            {
                enqueue(map[i][j]);
                map[i][j] = '.';
            }
        }
        
        int idx = 11;
        while(front != rear)
        {
            char temp = dequeue();
            map[idx--][j] = temp;
        }
    }
}
*/
 
void bomb(int x, int y, char color)
{
    int cnt = 0;
    vector<pair<int, int>> crash;
    
    visited[x][y] = 1;
    q.push({x, y});
    
    crash.push_back({x, y});
    cnt++;
    
    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] == color)
            {
                visited[xpos][ypos] = 1;
                q.push({xpos, ypos});
                
                crash.push_back({xpos, ypos});
                cnt++;
            }
        }
    }
    
    if(cnt >= 4)
    {
        for(int i = 0; i < crash.size(); i++)
        {
            map[crash[i].first][crash[i].second] = '.';
        }
        
        bombFlag = true;
    }
}
 
int main(void)
{
//    freopen("B11559_input.txt", "r", stdin);
    
    for(int i = 0; i < 12; i++)
    {
        for(int j = 0; j < 6; j++)
        {
            scanf(" %c", &map[i][j]);
        }
    }
    
    while(1)
    {
        bombFlag = false;
        bool breakFlag = true;
        
        memset(visited, 0, sizeof(visited));
        
        for(int i = 0; i < 12; i++)
        {
            for(int j = 0; j < 6; j++)
            {
                if(visited[i][j] == 0 && map[i][j] != '.')
                {            
                     bomb(i, j, map[i][j]);
                }
            }
        }
        
        if(bombFlag == true)
        {
            breakFlag = false;
            ans++;                                
        }
        
        if(breakFlag == true)
        {
            printf("%d", ans);
            break;
        }
        
        down();
    }
    
    return 0; 
}
cs
저작자표시 (새창열림)

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

[백준 3197] 백조의 호수 (BFS) (C/C++) (★★★)  (0) 2019.12.09
[백준 9019] DSLR (BFS) (C/C++)  (0) 2019.12.08
[백준 16234] 인구이동 (BFS) (C/C++) (★★)  (0) 2019.12.07
[백준 2573] 빙산 (BFS) (C/C++) (★)  (0) 2019.12.06
[백준 1389] 케빈 베이컨의 6단계 법칙 (BFS) (C/C++)  (0) 2019.12.06
#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 map[110][110];
int N, L, R;
 
queue<pair<int, int>> q;
int visited[110][110];
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && x < N && y >= 0 && y < N)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void init()
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            visited[i][j] = 0;
        }
    }    
}
 
int check()
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(visited[i][j] == 1)
            {
                return 0;
            }
        }
    }
    
    return 1;
}
 
void BFS(int x, int y)
{
    // 시간초과의 원인
    // int check[110][110] = {0};
    vector<pair<int, int>> check;
    
    q.push({x, y});
    
    int sum = 0;
    int cnt = 0;
    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 && L <= abs(map[xpos][ypos]-map[x][y]) && abs(map[xpos][ypos]-map[x][y]) <= R)
            {
                if(visited[x][y] == 0)
                {
                    // 시간초과의 원인
                    // check[x][y] = 1;
                    check.push_back({x, y});
                    
                    visited[x][y] = 1;
                    
                    sum += map[x][y];
                    cnt++;
                }
                
                if(visited[xpos][ypos] == 0)
                {
                    // 시간초과의 원인 
                    // check[xpos][ypos] = 1;
                    check.push_back({xpos, ypos});
                    
                    visited[xpos][ypos] = 1;
                    q.push({xpos, ypos});
                    
                    sum += map[xpos][ypos];
                    cnt++;
                }
            }
        }
    }
    
    // 시간초과의 원인 
    /*
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(check[i][j] == 1)
            {
                map[i][j] = sum/cnt;
            }
        }
    }
    */
    
    // 이동 후 초기화 
    for(int i = 0; i < check.size(); i++)
    {
        map[check[i].first][check[i].second] = sum/cnt;
    }
}
 
int main(void)
{
//    freopen("B16234_input.txt", "r", stdin);
    
    scanf("%d %d %d", &N, &L, &R);
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
    
    int ans = 0;
    while(1)
    {
//        init();
        memset(visited, 0 ,sizeof(visited));
        
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < N; j++)
            {
                if(visited[i][j] == 0)
                {
                    BFS(i, j);    
                }
            }
        }    
        
        if(check() == 1)
        {
            printf("%d", ans);
            break;
        }
        
        ans++;
    }
    
    return 0;
}
cs
저작자표시 (새창열림)

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

[백준 9019] DSLR (BFS) (C/C++)  (0) 2019.12.08
[백준 11559] Puyo Puyo (BFS) (C/C++) (★)  (0) 2019.12.08
[백준 2573] 빙산 (BFS) (C/C++) (★)  (0) 2019.12.06
[백준 1389] 케빈 베이컨의 6단계 법칙 (BFS) (C/C++)  (0) 2019.12.06
[백준 1261] 알고스팟 (BFS) (C/C++) (★)  (0) 2019.12.06
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
 
int map[310][310];
int mapCopy[310][310];
int visited[310][310];
int row, col;
int time;
 
queue<pair<int, int>> q;
 
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 init()
{
    for(int x = 0; x < row; x++)
    {
        for(int y = 0; y < col; y++)
        {
            int cnt = 0;
            
            for(int k = 0; k < 4; k++)
            {
                int xpos = x+dx[k];
                int ypos = y+dy[k];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 0)
                {
                    cnt++;        
                }
            }
            
            if(cnt != 0)
            {
                q.push({x, y});
            }
        }
    }
}
 
void melt()
{
    int size = q.size();
    
    while(size--)
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        int cnt = 0;
        
        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] == 0)
            {
                cnt++;
            }    
        }    
        
        mapCopy[x][y] -= cnt;
        
        if(mapCopy[x][y] < 0)
        {
            mapCopy[x][y] = 0;
        }    
    }
}
 
void check(int x, int y)
{
    queue<pair<int, int>> c;
    c.push({x, y});
    visited[x][y] = 1;
    
    while(!c.empty())
    {
        x = c.front().first;
        y = c.front().second;
        c.pop();
        
        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] != 0 && visited[xpos][ypos] == 0)
            {
                c.push({xpos, ypos});
                visited[xpos][ypos] = 1;
            }
        }
    }
}
 
int main(void)
{
//    freopen("B2589_input.txt", "r", stdin);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
            
            mapCopy[i][j] = map[i][j];
        }
    }
    
    while(1)
    {    
        time++;
        
        init();
        
        melt();
        
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                map[i][j] = mapCopy[i][j];
            }
        }
        
        int mapCnt = 0;
        memset(visited, 0, sizeof(visited));
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] != 0 && visited[i][j] == 0)
                {
                    check(i, j);
                    mapCnt++;
                }
            }
        }
        
        if(mapCnt >= 2)
        {
            cout << time;
            break;
        }
        else if(mapCnt == 0)
        {
            cout << "0";
            break;
        }
    }
    
    return 0;
}
 cs
저작자표시 (새창열림)

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

[백준 11559] Puyo Puyo (BFS) (C/C++) (★)  (0) 2019.12.08
[백준 16234] 인구이동 (BFS) (C/C++) (★★)  (0) 2019.12.07
[백준 1389] 케빈 베이컨의 6단계 법칙 (BFS) (C/C++)  (0) 2019.12.06
[백준 1261] 알고스팟 (BFS) (C/C++) (★)  (0) 2019.12.06
[백준 14395] 4연산 (BFS) (C/C++)  (0) 2019.12.06
#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int map[110][110];
int peopleNum;
int relation;
int Min = 9999999;
int ans;
 
queue<int> q;
int visited[110];
 
void init()
{
    for(int i = 1; i <= peopleNum; i++)
    {
        visited[i] = 0;
    }
}
 
void BFS(int start)
{
    visited[start] = 1;
    q.push(start);
    
    while(!q.empty())
    {
        start = q.front();
        q.pop();
        
        for(int i = 1; i <= peopleNum; i++)
        {
            if(map[start][i] == 1 && visited[i] == 0)
            {
                visited[i] = visited[start] + 1;
                q.push(i);
            }
        }
    }
}
 
int main(void)
{
//    freopen("B1389_input.txt", "r", stdin);
    
    scanf("%d %d", &peopleNum, &relation);
    
    for(int i = 1; i <= relation; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        
        map[a][b] = 1;
        map[b][a] = 1;
    }
    
    for(int i = 1; i <= peopleNum; i++)
    {
        init();
        
        BFS(i);
        
        int sum = 0;
        for(int j = 1; j <= peopleNum; j++)
        {
            if(i == j)
            {
                continue;
            }
            else
            {
                sum += (visited[j]-1);
            }
        }
                
        if(sum < Min)
        {
            Min = sum;
            ans = i;
        }
    }
 
    cout << ans;
    
    return 0;
}
cs
저작자표시 (새창열림)

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

[백준 16234] 인구이동 (BFS) (C/C++) (★★)  (0) 2019.12.07
[백준 2573] 빙산 (BFS) (C/C++) (★)  (0) 2019.12.06
[백준 1261] 알고스팟 (BFS) (C/C++) (★)  (0) 2019.12.06
[백준 14395] 4연산 (BFS) (C/C++)  (0) 2019.12.06
[백준 7576] 토마토 (BFS) (C/C++)  (0) 2019.12.06
#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
typedef struct node
{
    int x;
    int y;
    int crash;
}node;
 
int map[110][110];
int row, col;
int Min = 9999999;
 
queue<node> q;
int visited[110][110][210];
 
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()
{
    visited[0][0][0] = 1;
    q.push({0, 0, 0});
    
    while(!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        int crash = q.front().crash;
        q.pop();
        
        if(x == row-1 && y == col-1)
        {
            if(crash < Min)
            {
                Min = crash;
            }
        }
        
        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] == 0 && visited[xpos][ypos][crash] == 0 && crash <= row+col-2)
            {
                visited[xpos][ypos][crash] = 1;
                q.push({xpos, ypos, crash});
            }
            else if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 1 && visited[xpos][ypos][crash+1] == 0 && crash+1 <= row+col-2)
            {
                visited[xpos][ypos][crash+1] = 1;
                q.push({xpos, ypos, crash+1});
            }
        }
    }
}
 
int main(void)
{
//    freopen("B1261_input.txt", "r", stdin);
    
    scanf("%d %d", &col, &row);
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            scanf("%1d", &map[i][j]);
        }
    }
    
    BFS();
    
    printf("%d", Min);
        
    return 0;
}
cs
저작자표시 (새창열림)

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

[백준 2573] 빙산 (BFS) (C/C++) (★)  (0) 2019.12.06
[백준 1389] 케빈 베이컨의 6단계 법칙 (BFS) (C/C++)  (0) 2019.12.06
[백준 14395] 4연산 (BFS) (C/C++)  (0) 2019.12.06
[백준 7576] 토마토 (BFS) (C/C++)  (0) 2019.12.06
[백준 5427] 불 (BFS) (C/C++) (★)  (0) 2019.12.05
#include <stdio.h>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
long long startNum, endNum;
string ans;
bool flag = false;
 
queue<pair<long long, string>> q;
map<long long, int> visited;
 
void BFS()
{
    visited[startNum] = 1;
    q.push({startNum, ""});
    
    while(!q.empty())
    {
        long long num = q.front().first;
        string oper = q.front().second;
        q.pop();
        
        if(num == endNum)
        {
            flag = true;
            ans = oper;
            
            return;
        }
        
        for(int i = 1; i <= 4; i++)
        {
            long long numTemp = num;
            
            // *
            if(i == 1)
            {
                numTemp *= numTemp;
                
                if(visited[numTemp] == 0)
                {
                    visited[numTemp] = 1;
                    q.push({numTemp, oper+"*"});
                }
            }
            // +
            else if(i == 2)
            {
                numTemp += numTemp;
                
                if(visited[numTemp] == 0)
                {
                    visited[numTemp] = 1;
                    q.push({numTemp, oper+"+"});
                }
            }
            // -
            else if(i == 3)
            {
                numTemp -= numTemp;
                
                if(visited[numTemp] == 0)
                {
                    visited[numTemp] = 1;
                    q.push({numTemp, oper+"-"});
                }
            }
            // /
            else if(i == 4)
            {
                if(numTemp == 0)
                {
                    continue;
                }
                
                numTemp /= numTemp;
                
                if(visited[numTemp] == 0)
                {
                    visited[numTemp] = 1;
                    q.push({numTemp, oper+"/"});
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B14395_input.txt", "r", stdin);
    
    cin >> startNum >> endNum;
    
    if(startNum == endNum)
    {
        cout << "0" << endl;
        
        return 0;
    }
    
    BFS();
    
    if(flag == true)
    {
        cout << ans << endl;
    }
    else
    {
        cout << "-1" << endl;
    }
    
    return 0;
}
cs
저작자표시 (새창열림)

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

[백준 1389] 케빈 베이컨의 6단계 법칙 (BFS) (C/C++)  (0) 2019.12.06
[백준 1261] 알고스팟 (BFS) (C/C++) (★)  (0) 2019.12.06
[백준 7576] 토마토 (BFS) (C/C++)  (0) 2019.12.06
[백준 5427] 불 (BFS) (C/C++) (★)  (0) 2019.12.05
[백준 3055] 탈출 (BFS) (C/C++) (★)  (0) 2019.12.05

+ Recent posts

티스토리툴바