https://www.acmicpc.net/problem/1389

 

1389번: 케빈 베이컨의 6단계 법칙

첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다.

www.acmicpc.net

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main(){
	vector<int> arr[101];
	bool chk[101][101] = {0};
	int sum[101] = {0};
	int idx = 1;
	int n,m,t1,t2;
	
	cin >> n >> m;
	
	for(int i = 1; i <= m; i++){
		cin >> t1 >> t2;
		arr[t1].push_back(t2);
		arr[t2].push_back(t1);
	}
	
	for(int i = 1; i <= n; i++){
		queue<int> q;
		int cnt = 0;
		q.push(i);
		chk[i][i] = 1;
		
		while(!q.empty()){
			int q_size = q.size();
			cnt +=1;

			for(int k = 0; k < q_size; k++){
				int tmp = q.front(); q.pop();
				
				for(int j = 0; j < arr[tmp].size(); j++){
					if(chk[i][arr[tmp][j]]) continue;
					
					chk[i][arr[tmp][j]] = true;
					sum[i] += cnt;
					q.push(arr[tmp][j]);
				}
			}
		}
		
		if(sum[idx] > sum[i])
			idx = i;
	}
	
	cout << idx;

}

 

반응형

'프로그래밍 > 문제풀이' 카테고리의 다른 글

[bfs] 백준 2589 보물섬  (0) 2019.04.01
[dfs] 백준 11403 경로 찾기  (0) 2019.03.27
[dfs] 백준 2644 촌수계산  (0) 2019.03.27
[dfs] 백준 9903 로또  (0) 2019.03.27
[bfs, dfs] 백준 2573 빙산  (0) 2019.03.25

https://www.acmicpc.net/problem/2644


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <vector>
using namespace std;
vector<int> v[100];
bool visited[100] = {0};
bool chk = 0;
 
void dfs(int start, int target, int ret){
    if(start == target)    {cout << ret; chk = true;}
    
    for(int i = 0; i  <v[start].size(); i++){
        int tmp = v[start][i];
        
        if(visited[tmp]) continue;
        visited[tmp] = true;
        dfs(tmp,target,ret+1);
    }
 
}
 
int main(){
    int target1,target2,n,m,x,y;
    
    cin >> n >> target1 >> target2 >> m;
    
    for(int i = 0; i < m; i++){
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(target1,target2,0);
    if(!chk) cout << -1;
 
}
cs


반응형

'프로그래밍 > 문제풀이' 카테고리의 다른 글

[dfs] 백준 11403 경로 찾기  (0) 2019.03.27
[bfs] 백준 1389 케빈 베이컨의 6단계 법칙  (0) 2019.03.27
[dfs] 백준 9903 로또  (0) 2019.03.27
[bfs, dfs] 백준 2573 빙산  (0) 2019.03.25
[bfs, dfs] 백준 2667 단지번호붙이기  (0) 2019.03.24

https://www.acmicpc.net/problem/6603



간단한 dfs문제입니다.




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int arr[13];
int t = 0;
 
void dfs(int start, vector<int>& v){
    v.push_back(arr[start]);
    if(v.size() == 6){
        for(int i = 0; i < 6; i++)
            cout << v[i] << ' ';
        cout << endl;
        return;
    }
    
    for(int i = start+1; i < t; i++){
        dfs(i,v);
        v.pop_back();
    }
}
 
int main(){
    
    
    while(1){
 
        cin >> t;
        if(t==0) break;
        
        for(int i = 0; i < t; i++) cin >> arr[i];
        for(int i = 0; i < t; i++){
            vector<int> v;
            dfs(i,v);
        }
        cout << endl;
    }
}
 
cs


반응형

'프로그래밍 > 문제풀이' 카테고리의 다른 글

[bfs] 백준 1389 케빈 베이컨의 6단계 법칙  (0) 2019.03.27
[dfs] 백준 2644 촌수계산  (0) 2019.03.27
[bfs, dfs] 백준 2573 빙산  (0) 2019.03.25
[bfs, dfs] 백준 2667 단지번호붙이기  (0) 2019.03.24
[dfs] 백준 2606 바이러스  (0) 2019.03.22

https://www.acmicpc.net/problem/2573



bfs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <queue>
using namespace std;
 
int map[300][300] = {0};
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int n,m;
 
bool bfs_chk(){
    int cnt = 0;
    bool visited[300][300] = {0};
 
    queue<pair<int,int> > q;
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j  < m; j++){
            if(cnt >=2) return true;
            if(visited[i][j] || map[i][j] == 0) continue;
            cnt+=1;
            q.push({i,j}); visited[i][j] = 1;
            
            while(!q.empty()){
                int x= q.front().second, y = q.front().first;
                q.pop();
                
                for(int k = 0; k < 4; k++){
                    int xx = x + dx[k], yy = y + dy[k];
                    if(yy >= n || yy < 0 || xx >= m || xx < 0) continue;
                    if(map[yy][xx] == 0 || visited[yy][xx]) continue;
                    q.push({yy,xx}); visited[yy][xx] = 1;
                }
            }
        }
    }
    
    return false;
}
 
bool chk_zero(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(map[i][j] != 0) return false;
        }
    }
    return true;
}
 
int main(){
    int y = 0;
    int m_map[300][300] = {0};
    cin >> n >> m;
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j  < m; j++)
            cin >> map[i][j];        
    }
    
    while(1){
        if(chk_zero()){ cout << 0; break;}
        if(bfs_chk()){cout << y; break;}
        y+=1;
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(map[i][j] != 0){
                    int zero_cnt = 0;
                    for(int k = 0; k < 4; k++){
                        int x = j + dx[k] , y = i + dy[k];
                        if(map[y][x] == 0) zero_cnt+=1;
                    }
                    m_map[i][j] = zero_cnt;
                }
            }
        }
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(map[i][j] != 0){
                    map[i][j] -= m_map[i][j];
                    if(map[i][j] < 0) map[i][j] = 0;
                }
            }
        }
        
    }
}
cs


반응형

'프로그래밍 > 문제풀이' 카테고리의 다른 글

[dfs] 백준 2644 촌수계산  (0) 2019.03.27
[dfs] 백준 9903 로또  (0) 2019.03.27
[bfs, dfs] 백준 2667 단지번호붙이기  (0) 2019.03.24
[dfs] 백준 2606 바이러스  (0) 2019.03.22
[bfs] 백준 7569 토마토  (0) 2019.03.22

https://www.acmicpc.net/problem/2667



저에게 익숙한 bfs로 짠 코드 입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
 
int main(){
    char map[25][25];
    int ret[625] = {0};
    int n, idx= -1;
    queue<pair<int,int> > q;
    bool visited[25][25] = {0};
    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,1,-1};
 
    cin >> n;
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++) cin >> map[i][j];
    }
 
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(visited[i][j] || map[i][j] == '0') continue;
            
            idx+=1;
            q.push({i,j});
            visited[i][j] = 1;
            ret[idx] =0;
            
            while(!q.empty()){
                int x = q.front().second, y = q.front().first;
                q.pop();
                ret[idx] += 1;
                
                for(int k = 0; k < 4; k++){
                    int xx = x + dx[k], yy = y + dy[k];
                    
                    if(xx >= n || xx < 0 || yy >=n || yy < 0) continue;
                    if(visited[yy][xx] || map[yy][xx] == '0') continue;
                    
                    
                    q.push({yy,xx});
                    visited[yy][xx] = 1;
                }
            }
        }
    }
    
    sort(ret, ret+idx+1);
    
    cout << idx+1 << '\n';
    for(int i = 0; i <= idx; i++)
        cout << ret[i] << '\n';
}
cs


이번에 소학회에서 배운 dfs로 구현해봤습니다. 연습하면 dfs로 구현하는 것이 더 쉬울 것 같네요.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <algorithm>
using namespace std;
 
int ret[625] = {0}, n, idx=-1;
bool visited[25][25] = {0};
char map[25][25];
 
void dfs(int y, int x){
    if(y >= n || y < 0 || x >= n || x < 0 || map[y][x] =='0' || visited[y][x]) return;
    ret[idx]++;
    visited[y][x] = 1;
    dfs(y-1,x), dfs(y+1,x) , dfs(y,x-1), dfs(y,x+1);
}
 
int main(){
    cin >> n;
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++)
            cin >> map[i][j];
    }
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(visited[i][j] || map[i][j] == '0') continue;
            idx++;
            dfs(i,j);
        }
    }
    sort(ret, ret+idx+1);
    
    cout << idx+1 << '\n';
    for(int i = 0; i <= idx; i++)
        cout << ret[i] << '\n';
}
cs


반응형

'프로그래밍 > 문제풀이' 카테고리의 다른 글

[dfs] 백준 9903 로또  (0) 2019.03.27
[bfs, dfs] 백준 2573 빙산  (0) 2019.03.25
[dfs] 백준 2606 바이러스  (0) 2019.03.22
[bfs] 백준 7569 토마토  (0) 2019.03.22
[bfs] 라비다 1052 maze problem  (0) 2019.03.18

https://www.acmicpc.net/problem/2606

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <vector>
using namespace std;
 
int ret = 0;
vector<int> v[101];
bool visited[101] = {0};
 
 
void dfs(int start);
 
int main(){
    ios_base::sync_with_stdio(false);
    
    int com_n, n;
    
    cin >> com_n >> n;
 
    for(int i = 0; i < n; i++){
        int x,y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    
    dfs(1);
    
    cout << ret-1;
    
    return 0;
}
 
void dfs(int start){
    for(int i = 0; i < v[start].size(); i++){
        int tmp = v[start][i];
        
        if(visited[tmp])    continue;
        visited[tmp] = true;
        ret+=1;
        dfs(tmp);
    }
}
cs


반응형

'프로그래밍 > 문제풀이' 카테고리의 다른 글

[bfs, dfs] 백준 2573 빙산  (0) 2019.03.25
[bfs, dfs] 백준 2667 단지번호붙이기  (0) 2019.03.24
[bfs] 백준 7569 토마토  (0) 2019.03.22
[bfs] 라비다 1052 maze problem  (0) 2019.03.18
[dp] 백준 1495 기타리스트  (0) 2019.02.20

https://www.acmicpc.net/problem/7569


처음에 토마토가 들어가 있는 좌표를 queue에 push합니다.


그리고 queue에 있는 것을 하나 씩 꺼내서 bfs합니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <queue>
using namespace std;
 
int map[100][100][100];
int h,n,m;
 
bool chk(){
    for(int i = 0; i < h; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < m; k++){
                if(map[i][j][k] == 0) return true;
            }
        }
    }
    return false;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    
    bool visited[100][100][100] = {0};
    int dz[6] = {1,-1,0,0,0,0};
    int dy[6] = {0,0,1,-1,0,0};
    int dx[6] = {0,0,0,0,1,-1};
    queue<pair<int,pair<int,int> > > q;
    int day = -1;
    
    cin >> m >> n >> h;
    
    for(int i = 0; i < h; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < m; k++){
                cin >> map[i][j][k];
                if(map[i][j][k] == 1){
                    q.push({i,{j,k}});
                    visited[i][j][k] = true;
                }
            }
        }
    }
    
    if(!chk()){
        cout << 0;
        return 0;
    }
    
    while(!q.empty()){
        int size = q.size();
        day+=1;
        
        for(int i = 0; i < size; i++){
            int x = q.front().second.second, y = q.front().second.first, z = q.front().first;
            q.pop();
            for(int j = 0; j < 6; j++){
                int xx = x + dx[j], yy = y + dy[j], zz = z + dz[j];
                if(xx >= m || yy >= n || zz >= h || xx < 0 || yy < 0 || zz < 0) continue;
                if(visited[zz][yy][xx] || map[zz][yy][xx] == -1) continue;
                visited[zz][yy][xx] = true;
                map[zz][yy][xx] = 1;
                q.push({zz,{yy,xx}});
            }
        }
        
    }
    
    if(chk())    cout << -1;
    else cout << day;
    
}
cs


반응형

'프로그래밍 > 문제풀이' 카테고리의 다른 글

[bfs, dfs] 백준 2667 단지번호붙이기  (0) 2019.03.24
[dfs] 백준 2606 바이러스  (0) 2019.03.22
[bfs] 라비다 1052 maze problem  (0) 2019.03.18
[dp] 백준 1495 기타리스트  (0) 2019.02.20
[dp] 백준 1309 동물원  (0) 2019.02.02

https://judge.lavida.us/problem.php?id=1052


아주대 A.N.S.I에서 쓰는 저지 사이트입니다. 



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <queue>
using namespace std;
 
 
int main(){
    ios_base::sync_with_stdio(false);
    int t;
    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
    
    cin >> t;
    
    while(t--){
        char map[100][100];
        int n,m;
        pair<int,int> start;
        cin >> n >> m;
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cin >> map[i][j];
                if(map[i][j] == 'S')  start = {i,j};
            }
        }
        
        queue<pair<int,int> > q;
        bool visited[100][100] = {0};
        bool check_goal = 0;
        int count = 0;
        q.push(start);
        
        while(!q.empty() && !check_goal){
            int size = q.size();
            count++;
            
            for(int i = 0; i < size; i++){
                int x = q.front().second, y = q.front().first;
                q.pop();
                
                for(int i= 0; i  < 4; i++){
                    int xx = x  + dx[i], yy = y+dy[i];
                    
                    if(xx < 0 || yy < 0 || xx >= m || yy >= n) continue;
                    if(visited[yy][xx] || map[yy][xx] == '#') continue;
                    if(map[yy][xx] == 'E'){
                        check_goal = true;
                        break;
                    }
                    q.push({yy,xx});
                    visited[yy][xx] = true;
                }
            }
        }
        if(check_goal) cout << count << endl;
        else          cout << -1 << endl;
    }    
}
cs


간단히 bfs를 이용해 최단경로 찾는 문제입니다.

반응형

'프로그래밍 > 문제풀이' 카테고리의 다른 글

[dfs] 백준 2606 바이러스  (0) 2019.03.22
[bfs] 백준 7569 토마토  (0) 2019.03.22
[dp] 백준 1495 기타리스트  (0) 2019.02.20
[dp] 백준 1309 동물원  (0) 2019.02.02
[dp] 백준 2579 계단오르기  (0) 2019.02.02

https://www.acmicpc.net/problem/1495


다이나믹 프로그래밍을 이용헤서 풀었습니다.


dp를 이차원 배열로 해서 그 곡에 가능한 볼륨을 체크하는 방식으로 풀었습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
 
int main() {
    int n, s, m;
    bool dp[101][10001] = { {0,}, };
    int v[101];
    int ret = -1;
 
    cin >> n >> s >> m;
 
    for (int i = 1; i <= n; i++) cin >> v[i];
 
    if (s - v[1] >= 0) dp[1][s-v[1]] = true;
    if (s + v[1] <= m) dp[1][s+v[1]] = true;
 
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (dp[i - 1][j]) {
                if (j - v[i] >= 0) dp[i][j - v[i]] = true;
                if (j + v[i] <= m) dp[i][j + v[i]] = true;
            }
        }
    }
    
    for (int i = 0; i <= m; i++)
        if (dp[n][i]) ret = i;
    
    cout << ret;
 
}
cs


반응형

'프로그래밍 > 문제풀이' 카테고리의 다른 글

[bfs] 백준 7569 토마토  (0) 2019.03.22
[bfs] 라비다 1052 maze problem  (0) 2019.03.18
[dp] 백준 1309 동물원  (0) 2019.02.02
[dp] 백준 2579 계단오르기  (0) 2019.02.02
[etc] 백준 10757 큰 수 A+B  (0) 2019.01.29

https://www.acmicpc.net/problem/1309



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
 
int main(){
    int n;
    int dp[100001];
    
    cin >> n;
    
    dp[0] = 1; dp[1] = 3;
    for(int i = 2; i <= n; i++){
        dp[i] = dp[i-1]*2 + dp[i-2];
        dp[i]%=9901;
    }
    cout << dp[n];
}
cs


반응형

'프로그래밍 > 문제풀이' 카테고리의 다른 글

[bfs] 라비다 1052 maze problem  (0) 2019.03.18
[dp] 백준 1495 기타리스트  (0) 2019.02.20
[dp] 백준 2579 계단오르기  (0) 2019.02.02
[etc] 백준 10757 큰 수 A+B  (0) 2019.01.29
[etc] 백준 16678 모독  (0) 2019.01.27

+ Recent posts

티스토리툴바