How We Coding

Week 1 - DP1

Tutoring/PS2018. 6. 26. 15:43

<180625>


### DP Basic ###


1) [11051] 이항계수2 : http://boj.kr/11051


combi(n, r) : nCr 을 구하는 함수. nCr = n-1Cr + n-1Cr-1


<소스코드>

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
#include <stdio.h>
 
const int MOD=10007;
 
int d[1001][1001];
 
int combi(int n, int r)
{
    int *ret = &d[n][r];
    if(r == 0 || r == n) return 1;
    if(*ret != -1) return *ret;
 
    return *ret = (combi(n-1, r-1)+combi(n-1, r))%MOD;
}
 
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i=0; i<=n; i++)
        for(int j=0; j<=n; j++)
            d[i][j] = -1;
    printf("%d\n", combi(n, k));
    return 0;
}
cs



2) [11055] 가장 큰 증가하는 부분 수열 : http://boj.kr/11055


d[i] : i ~ (n-1) 번째까지의 수열 중에서 가장 큰 증가하는 부분 수열의 합의 최대값


<소스코드>

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
#include <stdio.h>
 
int n;
int a[1001], d[1001];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int lis(int s)
{
    int *ret = &d[s];
    if(s == n-1) return a[s];
    if(*ret) return *ret;
 
    *ret = a[s];
    for(int i=s+1; i<n; i++) {
        if(a[s] < a[i])
            *ret = max(*ret, a[s]+lis(i));
    }
    return *ret;
}
 
int main()
{
    int ans=0;
    scanf("%d", &n);
 
    for(int i=0; i<n; i++)
        scanf("%d", a+i);
 
    for(int i=0; i<n; i++)
        ans = max(ans, lis(i));
    printf("%d\n", ans); 
    return 0;
}
 
cs



3) [11048] 이동하기 : http://boj.kr/11048


d[i][j] : (i,j) 에서 이동해서 가져올 수 있는 사탕 갯수의 최대값


<소스코드>

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 <stdio.h>
 
int g[1001][1001];
int d[1001][1001];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int move(int r, int c)
{
    int *ret = &d[r][c];
    if(r <= 0 || c <= 0) return 0;
    if(*ret != -1) return *ret;
    
    *ret = move(r-1, c)+g[r][c];
    return *ret = max(*ret, move(r, c-1)+g[r][c]);
}
 
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
 
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            scanf("%d", &g[i][j]);
            d[i][j] = -1;
        }
    }
 
    printf("%d\n", move(n, m));
    return 0;
}
 
cs




4) [11066] 파일합치기 : http://boj.kr/11066


d[i][j] : i~j번째 까지의 파일을 합치는 데 드는 최소 비용


<소스코드>

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
#include <stdio.h>
 
int n, a[501];
int d[501][501];
int pSum[501];
 
int min(int a, int b)
{
    return a < b ? a : b;
}
 
int file(int s, int e)
{
    int *ret = &d[s][e];
    if(s == e) return 0;
    if(*ret != -1) return *ret;
 
    *ret = 0x7fffffff;
    for(int i=s; i<e; i++) 
        *ret = min(*ret, file(s, i)+file(i+1, e)); 
    return *ret = *ret + (pSum[e]-pSum[s-1]);
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        scanf("%d", &n);
        for(int i=1; i<=n; i++)
            pSum[i] = 0;
        for(int i=1; i<=n; i++) {
            scanf("%d", a+i);
            pSum[i] += (pSum[i-1]+a[i]);
 
            for(int j=1; j<=n; j++) 
                d[i][j] = -1;
        }
        printf("%d\n", file(1, n));
    }
 
    return 0;
}
 
cs


>> 누적합을 누적해나가야 한다.

>> pSum 을 초기화 안해서 뻣질 많이 함...ㅜㅜ



<180629>


1) [2410] 2의 멱수의 합 : http://boj.kr/2410



2) [2228] 구간 나누기 : http://boj.kr/2228


'Tutoring > PS' 카테고리의 다른 글

Week 7 - DFS+BFS  (0) 2018.04.07
Week 6 - BFS (숨박꼭질)  (0) 2018.03.30
Week 5 - BFS  (0) 2018.03.24
Week 4 - BFS  (0) 2018.03.11
Week3 - DFS  (0) 2018.03.07

Week 7 - DFS+BFS

Tutoring/PS2018. 4. 7. 00:26

<>


Week 7 : DFS+BFS


[2146] 다리 만들기 (http://boj.kr/2146) 


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
88
89
90
91
92
93
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
 
struct P { int r, c; };
 
int n;
int g[101][101];
int checked[101][101];
 
int dr[]={1, 0, -1, 0};
int dc[]={0, 1, 0, -1};
 
int min(int a, int b)
{
    return a < b ? a : b;
}
 
bool safe(int r, int c)
{
    return (0 <= r && r < n) && (0 <= c && c < n);
}
 
void dfs(queue<P> &q, int r, int c, int cnt)
{
    g[r][c] = cnt;
 
    for(int k=0; k<4; k++) {
        int nr = r+dr[k];
        int nc = c+dc[k];
        if(safe(nr, nc)) {
            if(g[nr][nc] == 1) { 
                dfs(q, nr, nc, cnt);
            }
            else {// g[nr][nc] == 0
                if(!checked[nr][nc]) {   
                    q.push((P){nr, nc});
                    checked[nr][nc] = 1;
                }
            }
        }
    }
}
 
int bfs(queue<P> &q, int cnt)
{
    while(!q.empty()) {
        int curR = q.front().r;
        int curC = q.front().c; q.pop();
 
        for(int k=0; k<4; k++) {
            int nr = curR + dr[k];
            int nc = curC + dc[k];
            if(safe(nr, nc) && g[nr][nc] != cnt && !checked[nr][nc]) {
                checked[nr][nc] = checked[curR][curC]+1;
                q.push((P){nr, nc});
                if(g[nr][nc] != 0) {
                    return checked[curR][curC];
                }
            }
        }
    }
    return 1e9;
}
 
int main()
{
    scanf("%d", &n);
 
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            scanf("%d", &g[i][j]);
 
    int cnt = 1;
    int ans = 1e9;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(g[i][j] == 1) {
                cnt++;
 
                queue<P> q;
                dfs(q, i, j, cnt); 
 
                int tmp = bfs(q, cnt);
                ans = min(ans, tmp);
 
                memset(checked, 0, sizeof(checked));                
            }                
        }
    }
    printf("%d\n", ans);
}
cs


>> 일단 하나의 섬을 하나의 컴퍼넌트로 체크를 하고, 섬 주위의 바다(0) 을 큐에 담는다.

>> 큐에 담긴 바다를 시작으로 거리를 잰다. 이때 현재섬이 아닌 섬을 만난 경우, 현재섬으로부터의 최소거리가 되므로 그 거리를 리턴한다.

>> 현재섬에는 cnt 값이 들어있다.



[]



[2573] 빙산 : http://boj.kr/2573 


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
88
89
90
91
#include <cstdio>
#include <queue>
using namespace std;
 
struct P { int r, c; };
struct M { int r, c, cnt; };
 
int r, c;
int g[301][301];
int dr[] = {1, 0, -1, 0};
int dc[] = {0, 1, 0, -1};
int visited[301][301];
 
queue<P> q;
 
void dfs(int i, int j, int &ans)
{
    visited[i][j] = ans;
    
    for(int k=0; k<4; k++) {
        int ni = i+dr[k];
        int nj = j+dc[k];
        if(g[ni][nj] && visited[ni][nj]!=ans)
            dfs(ni, nj, ans);
    }
}
 
int solve(int sum)
{
    int ans=0;
    while(sum) {
        ans++;
        queue<M> mq;
        while(!q.empty()) {
            int curR = q.front().r;
            int curC = q.front().c; q.pop();
 
            int cnt = 0;
            for(int k=0; k<4; k++) {
                int nr = curR + dr[k];
                int nc = curC + dc[k];
                if(!g[nr][nc]) cnt++;
            }
            mq.push((M){curR, curC, cnt});    
        }
 
        while(!mq.empty()) {
            int curR = mq.front().r;
            int curC = mq.front().c;
            int cnt = mq.front().cnt; mq.pop();
 
            if(g[curR][curC] > cnt) {
                q.push((P){curR, curC});
                g[curR][curC] -= cnt;
                sum -= cnt;
            }
            else {
                sum -= g[curR][curC];
                g[curR][curC] = 0;
            }
        }
 
        int cnt=0;
        for(int i=0; i<r; i++) {
            for(int j=0; j<c; j++) {
                if(g[i][j] && visited[i][j]!=ans) {
                    cnt++;
                    dfs(i, j, ans);
                    if(cnt == 2) return ans;
                }
            }
        }
    } 
    return 0;
}
 
int main()
{
    scanf("%d%d", &r, &c);
 
    int sum = 0;
    for(int i=0; i<r; i++) {
        for(int j=0; j<c; j++) {
            scanf("%d", &g[i][j]);
            if(g[i][j]) q.push((P){i, j});
            sum += g[i][j];
        }
    }
 
    printf("%d\n", solve(sum));
}
cs


>> 1년전엔 그렇게나 틀렸는데, 이번엔 바로 풀었다. (한번 틀렸는데, 문제 이해를 잘못해서...)

>> 빙산을 일단 q에 담고, 주변에 바다가 얼마나 둘러싸여있는지 mq 에 담은 다음, 녹인다. 그리고 섬이 분리가 되었는지 확인한다.


[4179] 불! : http://boj.kr/4179


'Tutoring > PS' 카테고리의 다른 글

Week 1 - DP1  (0) 2018.06.26
Week 6 - BFS (숨박꼭질)  (0) 2018.03.30
Week 5 - BFS  (0) 2018.03.24
Week 4 - BFS  (0) 2018.03.11
Week3 - DFS  (0) 2018.03.07

Week 6 - BFS (숨박꼭질)

Tutoring/PS2018. 3. 30. 13:29

<180331>   


Week 6 - BFS


[12851] 숨박꼭질2 (http://boj.kr/12851)


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
c#include <cstdio>
#include <queue>
using namespace std;
 
const int MAX = 100001;
 
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
 
    queue<int> q;
    q.push(n);
 
    int visited[MAX]={0};
    
    int ok=0, ans=-1, cnt=0;
    while(!q.empty()) {
        int sz = q.size();
        ans++;
        for(int i=0; i<sz; i++) {
            int cur = q.front(); q.pop();
            visited[cur] = 1;
           
            if(cur == k) {
                ok = 1;
                cnt++;
                continue;
            }
 
            int next = cur+1; 
            if(next < MAX && !visited[next]) { q.push(next); }
 
            next = cur-1;
            if(0 <= next && !visited[next]) { q.push(next); }
            
            next = cur*2;
            if(next < MAX && !visited[next]) { q.push(next); }
        }
        if(ok) break;
    }
    printf("%d\n%d\n", ans,  cnt); 
}
cs


>> 방문체크를 꺼내면서 해야한다. 

>> ans 는 트리에서 레벨수회를 할 때 그 레벨을 세는 역할을 한다고 생각하면 될 것 같다.



[13529] 숨박꼭질3 (http://boj.kr/13549)


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
#include <cstdio>
#include <queue>
using namespace std;
 
const int MAX = 100001;
 
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
 
    queue<int> q;
    q.push(n);
 
    int visited[MAX]={0};
    visited[n] = 1;
 
    while(!q.empty()) {
        int cur = q.front(); q.pop();
 
        int next = cur+1;
        if(next < MAX && (!visited[next] || visited[next]>visited[cur]+1)) {
            q.push(next);
            visited[next] = visited[cur]+1;
        }
        
        next = cur-1;
        if(0 <= next && (!visited[next] || visited[next]>visited[cur]+1)) {
            q.push(next);
            visited[next] = visited[cur]+1;
        }
        
        next = cur*2;
        if(next < MAX && (!visited[next] || visited[next]>visited[cur])) {
            q.push(next);
            visited[next] = visited[cur];
        }
    }
    printf("%d\n", visited[k]-1);
}
cs


>> 정답이 언제든 갱신될 수 있다고 생각했다. 그래서 다 돌리고 난 뒤에 저장되어 있는 값이 정답이라고 생각한 것을 코드로 옮겼다.

>> 다음에 방문할 위치가 현재위치보다 적은 시간에 방문할 수 있다면 다시 방문해야한다.



[13913] 숨박꼭질4 (http://boj.kr/13913)


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 <cstdio>
#include <queue>
using namespace std;
 
const int MAX = 100001;
 
int n, k, from[MAX];
 
void trace(int cur)
{
    if(cur == n) { 
        printf("%d", cur);
        return ;
    }
    trace(from[cur]);
    printf(" %d", cur);
}
 
int main()
{
    scanf("%d%d", &n, &k);
 
    queue<int> q;
    q.push(n);
 
    int visited[MAX]={0};
    visited[n] = 1;
 
    while(!q.empty()) {
        int cur = q.front(); q.pop();
 
        int next = cur+1;
        if(next < MAX && !visited[next]) {
            q.push(next);
            visited[next] = visited[cur]+1;
            from[next] = cur;
            if(cur == k) break;
        }
        
        next = cur-1;
        if(0 <= next && !visited[next]) {
            q.push(next);
            visited[next] = visited[cur]+1;
            from[next] = cur;
            if(cur == k) break;
        }
        
        next = cur*2;
        if(next < MAX && !visited[next]) {
            q.push(next);
            visited[next] = visited[cur]+1;
            from[next] = cur;
            if(cur == k) break;
        }
    }
    printf("%d\n", visited[k]-1);
    trace(k);
}
cs


>> from 배열에 주목하자.

>> from[next] = cur; 은 next 의 이전 위치는 cur 이란 뜻이다.

'Tutoring > PS' 카테고리의 다른 글

Week 1 - DP1  (0) 2018.06.26
Week 7 - DFS+BFS  (0) 2018.04.07
Week 5 - BFS  (0) 2018.03.24
Week 4 - BFS  (0) 2018.03.11
Week3 - DFS  (0) 2018.03.07

Week 5 - BFS

Tutoring/PS2018. 3. 24. 11:31

<180324>



Week5 - BFS



[6593] 상범빌딩 (http://boj.kr/6593)


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
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
struct P { int L, R, C; };
 
int L, R, C;
int dl[]={1, -1, 0, 0, 0, 0};
int dr[]={0, 0, 1, -1, 0, 0};
int dc[]={0, 0, 0, 0, 1, -1};
 
bool safe(int l, int r, int c)
{
    return (0 <= l && l < 30) && (0 <= r && r < 30) && (0 <= c && c < 30);
}
 
int main()
{
    while(1) {
 
        scanf("%d%d%d", &L, &R, &C);
 
        if(!L && !R && !C) break;
 
        P s, e;
        char g[31][31][31];
        for(int l=0; l<L; l++) {
            for(int r=0; r<R; r++) 
                scanf("%s", g[l][r]);
            for(int r=0; r<R; r++) {
                for(int c=0; c<C; c++) {
                    if(g[l][r][c] == 'S')
                        s = (P){l, r, c};
                    if(g[l][r][c] == 'E') {
                        g[l][r][c] = '.';
                        e = (P){l, r, c};
                    }
                }
            }
        }
 
        queue<P> q;
        q.push(s);
        
        int visited[31][31][31]={0};
        visited[s.L][s.R][s.C] = 1;
 
        while(!q.empty()) {
            int curL = q.front().L;
            int curR = q.front().R;
            int curC = q.front().C; q.pop();
            
            if(curL == e.L && curR == e.R && curC == e.C) break;
 
            for(int k=0; k<6; k++) {
                int nL = curL+dl[k];
                int nR = curR+dr[k];
                int nC = curC+dc[k];
                if(safe(nL, nR, nC) && g[nL][nR][nC]=='.' && !visited[nL][nR][nC]) {
                    visited[nL][nR][nC] = visited[curL][curR][curC]+1;
                    q.push((P){nL, nR, nC});
                }
            }
        }
        
        int ans = visited[e.L][e.R][e.C];
        if(!ans) puts("Trapped!");
        else printf("Escaped in %d minute(s).\n", ans-1);
    }
}
cs


>> 3차원을 확장되었을 뿐, 이전 문제들과 동일하다.

>> 36번줄에 대해 처리를 안하면 답이 안나온다...



[5014] 스타트링크 (http://boj.kr/5014)


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 <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
int F, S, G, U, D;
int visited[1000001];
 
int main()
{
    scanf("%d%d%d%d%d", &F, &S, &G, &U, &D);
 
    queue<int> q;
    q.push(S);
    visited[S] = 1;
 
    while(!q.empty()) {
        int cur = q.front(); q.pop();
        
        if(cur == G) break;
 
        int next = cur+U;
        if(next < 1000001 && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; }
 
        next = cur-D;
        if(0 <= next && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; }
    }
    
    if(!visited[G]) puts("use the stairs");
    else printf("%d\n", visited[G]-1);
}
cs




[]

'Tutoring > PS' 카테고리의 다른 글

Week 7 - DFS+BFS  (0) 2018.04.07
Week 6 - BFS (숨박꼭질)  (0) 2018.03.30
Week 4 - BFS  (0) 2018.03.11
Week3 - DFS  (0) 2018.03.07
Week 2 - DFS  (0) 2018.02.21

Week 4 - BFS

Tutoring/PS2018. 3. 11. 01:04

<180324>



Week4 - BFS


[1260] DFS와 BFS




[1012] 유기농 배추





[2178] 미로탐색 (http://boj.kr/2178)


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
#include <cstdio>
#include <queue>
using namespace std;
 
struct P { int r, c; };
 
int r, c;
int g[102][102];
int dr[] = {1, 0, -1, 0};
int dc[] = {0, 1, 0, -1};
 
int main()
{
    scanf("%d%d", &r, &c);
 
    for(int i=1; i<=r; i++)
        for(int j=1; j<=c; j++)
            scanf("%1d", &g[i][j]);
 
    queue<P> q;  
    q.push((P){1, 1});
 
    while(!q.empty()) {
        int curR = q.front().r;
        int curC = q.front().c; q.pop();
 
        for(int k=0; k<4; k++) {
            int nr = curR + dr[k];
            int nc = curC + dc[k];
            if(g[nr][nc] == 1) {
                q.push((P){nr, nc});
                g[nr][nc] = g[curR][curC]+1;
            }
        }
    }
 
    printf("%d\n", g[r][c]);
}
cs


>> input data 특성상 visited[r][c] 배열을 만들 필요가 없다.

>> 32 라인이 이 문제의 핵심인 것 같다.

>> 21, 31 : 구조체 변수의 경우 저런식으로 캐스팅 해서 바로 넣을 수 있다.



[2644] 촌수계산 (http://boj.kr/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
35
36
37
38
39
40
41
#include <cstdio>
#include <vector>
#include <queue>
 
using namespace std;
 
int main()
{
    int n, m;
    int s, e;
    scanf("%d%d%d%d", &n, &s, &e, &m);
 
    vector<int> v[101];
    while(m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
 
    queue<int> q;
    q.push(s);
 
    int visited[101]={0};
    visited[s] = 1;
    
    while(!q.empty()) {
        int cur = q.front(); q.pop();
        if(cur == e) break;
 
        for(int i=0; i<v[cur].size(); i++) {
            int next = v[cur][i];
            if(!visited[next]) {
                visited[next] = visited[cur]+1;
                q.push(next);
            }
        }
    }
    printf("%d\n", visited[e]-1);
}
 
cs


>> 알고리즘은 위 문제와 다를게 없음.


- 2년전 풀이..

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
#include <stdio.h>
 
int n, a, b, m, g[101], ck[101], ans;
 
int getPidx(int idx)
{
    if(idx == g[idx])
        return idx;
 
    return getPidx(g[idx]);
}
 
int main()
{
    int i, x, y, p;
    scanf("%d %d %d %d", &n, &a, &b, &m);
    
    for(i=1; i<=n; i++) 
        g[i] = i;
 
    while(m--) {
        scanf("%d %d", &x, &y);
        g[y] = x;
    }
    
    x = getPidx(a);
    y = getPidx(b);
 
    if(x != y)
        puts("-1");
    else {
        p = a;
        ck[a] = 1;
        do {
            p = g[p];
            ck[p] = 1;
        } while(p != x);
        
        p = b;
        while(!ck[p]) {
            p = g[p];
        }
        
        while(p != a) {
            ans++;
            a = g[a];
        }
 
        while(p != b) {
            ans++;
            b = g[b];
        }
        printf("%d\n", ans);
    }
 
    return 0;
}
cs


>> 2년전에는 위와 같이 풀었다. 공통 조상이 같으면 촌수를 구할 수 있고, 그렇지 않으면 불가능.

>> ...



[7562] 나이트의 이동 (http://boj.kr/7562)


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
#include <cstdio>
#include <queue>
using namespace std;
 
struct P { int i, j; };
 
int n;
int di[]={1, 1, 2, 2, -1, -1, -2, -2};
int dj[]={2, -2, 1, -1, 2, -2, 1, -1};
 
bool safe(int i, int j)
{
    return (0 <= i && i < n) && (0 <= j && j < n);
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int curI, curJ;
        int tI, tJ;
        int visited[305][305]={0};
 
        scanf("%d%d%d%d%d", &n, &curI, &curJ, &tI, &tJ);
 
        queue<P> q;
        q.push((P){curI, curJ});
        visited[curI][curJ] = 1;
 
        while(!q.empty()) {
            curI = q.front().i;
            curJ = q.front().j; q.pop();
 
            if(curI == tI && curJ == tJ) break;
 
            for(int k=0; k<8; k++) {
                int ni = curI+di[k];
                int nj = curJ+dj[k];
                if(safe(ni, nj) && !visited[ni][nj]) {
                    q.push((P){ni, nj});
                    visited[ni][nj] = visited[curI][curJ]+1;
                }
            }
        }
        printf("%d\n", visited[tI][tJ]-1);
    }
}
 
 
cs


>> 알고리즘은 미로탐색과 일치한다. 탐색 방범만 조금 다를뿐.



[1697] 숨박꼭질 (http://boj.kr/1697)


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 <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
bool safe(int k)
{
    return (0 <= k && k <= 100000);
}
 
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
 
    queue<int> q;
    q.push(n);
 
    int visited[100001]={0};
    visited[n] = 1;
 
    while(!q.empty()) {
        int cur = q.front(); q.pop();
        if(cur == k) break;
       
        int next = cur+1;
        if(safe(next) && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; } 
        
        next = cur-1;
        if(safe(next) && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; } 
 
        next = cur*2;
        if(safe(next) && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; } 
    }
    printf("%d\n", visited[k]-1);
}
cs


>> 동일한 알고리즘이다.

'Tutoring > PS' 카테고리의 다른 글

Week 6 - BFS (숨박꼭질)  (0) 2018.03.30
Week 5 - BFS  (0) 2018.03.24
Week3 - DFS  (0) 2018.03.07
Week 2 - DFS  (0) 2018.02.21
Week 1 - DFS  (0) 2018.02.20

Week3 - DFS

Tutoring/PS2018. 3. 7. 16:44

<180310>


Week3 - DFS


[1743] 음식물 피하기 (http://boj.kr/1732)


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 <stdio.h>
 
int n, m;
int g[101][101];
int dr[]={1, 0, -1, 0};
int dc[]={0, 1, 0, -1};
 
int safe(int a, int b)
{
    return (0 < a && a <= n) && (0 < b && b <= m);
}
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int dfs(int r, int c)
{
    int k, ret=1;
    g[r][c] = 0;
    
    for(k=0; k<4; k++) {
        int nr = r+dr[k];
        int nc = c+dc[k];
        if(safe(nr, nc) && g[nr][nc])
            ret += dfs(nr, nc);
    }
    return ret;
}
 
int main()
{
    int i, j, k;
    int ans=0;
    scanf("%d%d%d", &n, &m, &k);
    
    while(k--) {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a][b] = 1;
    }
 
    for(i=1; i<=n; i++) {
        for(j=1; j<=m; j++) {
            if(g[i][j]) {
                ans = max(ans, dfs(i, j));
            }
        }
    }
 
    printf("%d\n", ans);
    return 0;
}
 
cs



[2468] 안전영역 (http://boj.kr/2468)


1)


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
#include <stdio.h>
 
int n;
int g[101][101];
int visited[101][101];
int di[]={0, 1, 0, -1};
int dj[]={1, 0, -1, 0};
 
int safe(int i, int j)
{
    return (0 <= i && i < n) && (0 <= j && j < n);
}
 
void dfs(int i, int j, int k)
{
    visited[i][j] = k;
 
    for(int a=0; a<4; a++) {
        int ni = i+di[a];
        int nj = j+dj[a];
        if(safe(ni, nj) && g[ni][nj] >= k && visited[ni][nj] != k) 
            dfs(ni, nj, k);
    }
}
 
int main()
{
    int i, j, k;
    int max=1, min=100;
    int ans=0;
    scanf("%d", &n);
 
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            scanf("%d", &k);
            if(max < k) max = k;
            if(min > k) min = k;
            g[i][j] = k;
        }
    }
 
    for(k=min; k<=max; k++) {
        int tmp=0;
        for(i=0; i<n; i++) {
            for(j=0; j<n; j++) {
                if(g[i][j] >= k && visited[i][j] != k) {
                    tmp++;
                    dfs(i, j, k);
                }
            }
        }
        if(ans < tmp) ans = tmp; 
    }
    printf("%d\n", ans);
    return 0;
}
cs


>> 42 라인에서 k<max 로 해서 한번 틀렸음.

이렇게 할 경우 

2

1 1

1 1

의 테케의 정답은 1인데 0이나옴.


2) 1년 전 풀이


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
#include <stdio.h>
 
int n, ans, g[100][100], ck[100][100];
 
int safe(int x, int y)
{
    return (0 <= x && x < n) && (0 <= y && y < n); 
}
 
void dfs(int y, int x, int k)
{
    int i, xx, yy, dx[]={1, 0, -1, 0}, dy[]={0, 1, 0, -1};
    ck[y][x] = 1;
 
    for(i=0; i<4; i++) {
        xx = x+dx[i];
        yy = y+dy[i];
        if(safe(xx, yy) && g[yy][xx] > k && !ck[yy][xx])
            dfs(yy, xx, k);
    }
}
 
int main()
{
    int i, j, k, max=0;
    scanf("%d", &n);
 
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            scanf("%d", &g[i][j]);
            if(g[i][j] > max)
                max = g[i][j];
        }
    }
 
    for(k=0; k<max; k++) {
        int cnt=0;
        for(i=0; i<n; i++) {
            for(j=0; j<n; j++) {
                if(g[i][j] > k && !ck[i][j]) {
                    dfs(i, j, k);
                    cnt++;
                }
            }
        }
        
        if(ans < cnt)
            ans = cnt;
 
        for(i=0; i<n; i++)
            for(j=0; j<n; j++)
                ck[i][j] = 0;
    }
 
    printf("%d\n", ans);
    return 0;
}
cs


>> 거의 비슷하게 푼것 같다.



[11403] 경로찾기 (http://boj.kr/11403)


1) 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
40
41
42
43
44
45
46
#include <stdio.h>
 
int n, g[101][101];
int visited[101];
int ans[101][101];
 
int dfs(int s, int e)
{
    int ret=0;
    visited[s] = 1;
 
    for(int i=0; i<n; i++) {
        if(g[s][i]) {
            if(i == e) return 1;
            if(!visited[i]) ret = dfs(i, e);
            if(ret) return 1;
        }
    }
    return ret;
}
 
int main()
{
    scanf("%d", &n);
 
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            scanf("%d", &g[i][j]);
    
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            ans[i][j] = dfs(i, j);
            for(int k=0; k<n; k++)
                visited[k] = 0;
        }
    }
 
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++)
            printf("%d ", ans[i][j]);
        puts("");
    }
 
    return 0;
}
 
cs


>> dfs(i, j) : i 에서 j로 가는 길이 있는지 알려주는 함수.

>> 13, 14 : s 에서 i로 가는 길이 있는데, i가 e 라면, s에서 e로 가는 길이 있다는 뜻!!


2) 플로이드 풀이


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
#include <stdio.h>
 
int g[101][101];
 
int main()
{
    int i, j, k, n;
    scanf("%d", &n);
 
    for(i=0; i<n; i++)  
        for(j=0; j<n; j++) 
            scanf("%d", &g[i][j]);
    
 
    for(k=0; k<n; k++)
        for(i=0; i<n; i++)
            for(j=0; j<n; j++)
                if(g[i][k] && g[k][j])
                    g[i][j] = 1;
    
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++)
            printf("%d ", g[i][j]);
        puts("");
    }
 
    return 0;
}
cs


>> 플로이드 와샬 풀이가 좀더 직관적이긴 하다. 코드도 심플하고.

>> 하지만 DFS 로 풀수 있다고 해서 과제로 내주었다...얘들아 미안..ㅎㅎ

>> 18, 19 : i 에서 k로 가는 길이 있는데, k에서 j로 가는 길이 있으면 i 에서 j로 가는 길이 있다..!!



[9466] 텀 프로젝트


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
#include <stdio.h>
 
int ans;
int p[100001];
int visited[100001], finished[100001];
 
void dfs(int s)
{
    int next = p[s];
    visited[s] = 1;
    
    if(!visited[next]) dfs(next);
    else {
        if(!finished[next]) {
            for(int i=next; !finished[i]; i=p[i]) {
                finished[i] = 1;
                ans++;
            }
        }
    }
    finished[s] = 1;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
    while(tc--) {
        int n, k;
        scanf("%d", &n);
 
        for(int i=1; i<=n; i++) {
            scanf("%d", &k);
            p[i] = k;
            visited[i] = finished[i] = 0;
        }
 
        ans = 0;
        for(int i=1; i<=n; i++)
            if(!visited[i])
                dfs(i);
        
        printf("%d\n", n-ans);
    }
    return 0;
}
cs


>> 예전에 엄청 고통 받았던 문제..

>> 여전히 고통스럽다.

>> 결국 라이님의 블로그 설명을 보고 해결했었다. (https://kks227.blog.me/221028710658)


>> 사이클에 대한 처리를 배열하나를 더 만들어서 해야한다.


>> visited[next] = finished[next] = 0 : 아직 방문하지 않은 정점

>> visited[next] = 1 && finished[next] = 0 : 현재 정점과 next가 하나의 싸이클에 속함.

>> visited[next] = finished[next] = 1 : 이미 모든 탐색이 끝난 정점. 현재 정점은 next 가 그 싸이클 안에 있건 없건 절대 그 싸이클 안에 있을 수 없음.



[1707] 이분 그래프 (http://boj.kr/1707)


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
#include <cstdio>
#include <vector>
using namespace std;
 
int ans;
 
void isBinaryGraph(vector<int> g[], vector<int> &visited, int s, int ck)
{
    
    visited[s] = ck%2+1;
 
    for(int i=0; i<g[s].size() && ans; i++) {
        int next = g[s][i];
        if(!visited[next]) {
            isBinaryGraph(g, visited, next, ck+1);
        }
        else {
            if(visited[s] == visited[next]) {
                ans = 0;
                return ;
            }
        }
    }
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
    
    while(tc--) {
        int v, e;
        scanf("%d%d", &v, &e);
 
        vector<int> g[20001];
        vector<int> visited(v+1, 0);
 
        while(e--) {
            int a, b;
            scanf("%d%d", &a, &b);
            g[a].push_back(b);
            g[b].push_back(a);
        }
        
        ans = 1;
        for(int i=1; i<=v; i++) {
            if(!visited[i] && ans)
                isBinaryGraph(g, visited, i, 0);
        }
        ans ? puts("YES") : puts("NO");
    }
}
cs


>> 방문체크를 1과 2로 처리하였다. 

>> 다음에 방문할 정점이 이미 방문을 한 정점인데, 같은 번호로 방문체크가 되어 있으면 이분그래프가 아니다.

>> 46 : 컴퍼넌트는 여러개일 수 있다..


'Tutoring > PS' 카테고리의 다른 글

Week 6 - BFS (숨박꼭질)  (0) 2018.03.30
Week 5 - BFS  (0) 2018.03.24
Week 4 - BFS  (0) 2018.03.11
Week 2 - DFS  (0) 2018.02.21
Week 1 - DFS  (0) 2018.02.20

Week 2 - DFS

Tutoring/PS2018. 2. 21. 16:36

<180226>


Week 2 : DFS


[11724] 연결요소의 개수 (http://boj.kr/11724)


1)


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 <stdio.h>
 
int n, m;
int g[1001][1001];
int visited[1001];
 
void dfs(int s)
{
    int i;
    visited[s] = 1;
 
    for(i=1; i<=n; i++) {
        if(g[s][i] && !visited[i])
            dfs(i);
    }
 
}
 
int main()
{
    int i, ans=0;
    scanf("%d%d", &n, &m);
 
    while(m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a][b] = g[b][a] = 1;
    }
 
    for(i=1; i<=n; i++) {
        if(!visited[i]) {
            ans++;
            dfs(i);
        }
    }
    printf("%d\n", ans);
    return 0;
}
 
cs


>> DFS 기본 

>> 모든 정점에 대해서 DFS() 실행한 횟수가 컴퍼넌트의 갯수가 된다.


2) 연결리스트를 이용한 구현


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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct node {
    int v;
    struct node *next;
} Node;
 
typedef struct list {
    Node *head;
} List;
 
void init(List *list)
{
    list->head = NULL;
}
 
void addNode(List *list, int v)
{
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->v = v;
    newNode->next = list->head;
    list->head = newNode;
}
 
int n, m;
List g[1001];
int visited[1001];
 
void dfs(int s)
{
    Node *cur = g[s].head;
    visited[s] = 1;
 
    while(cur != NULL) {
        int next = cur->v;
        if(!visited[next]) dfs(next);
        else cur = cur->next;
    }
}
 
int main()
{
    int i, ans=0;
    scanf("%d%d", &n, &m);
 
    for(i=0; i<=n; i++)
        init(g+i);
 
    while(m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        addNode(g+a, b);
        addNode(g+b, a);
    }
      
    for(i=1; i<=n; i++) {
        if(!visited[i]) {
            ans++;
            dfs(i);
        }
    }
    printf("%d\n", ans);
    return 0;
}
 
cs




[10026] 적록색약 


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
#include <stdio.h>
 
int n;
char g[101][101];
int visited[101][101];
int di[]={1, 0, -1, 0};
int dj[]={0, 1, 0, -1};
 
int safe(int i, int j)
{
    return (0 <= i && i < n) && (0 <= j && j < n);
}
 
void dfs(int i, int j, char color)
{
    int k;
    visited[i][j] = 1;
    for(k=0; k<4; k++) {
        int ni = i+di[k];
        int nj = j+dj[k];
        if(safe(ni, nj) && !visited[ni][nj] && g[ni][nj] == color)
            dfs(ni, nj, color);
    }
}
 
void go()
{
    int i, j, ans=0;
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
           if(!visited[i][j]) {
                ans++;
                dfs(i, j, g[i][j]);
           }
        }
    }
    printf("%d\n", ans);
}
 
int main()
{
    int i, j;
    int rb=0, rgb=0;
    scanf("%d", &n);
 
    for(i=0; i<n; i++)
        scanf("%s", g[i]);
 
    go();
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            visited[i][j] = 0;
            if(g[i][j] == 'G')
                g[i][j] = 'R';
        }
    }
    
    go();
    return 0;
}
 
cs


>> 



[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
#include <stdio.h>
 
int n, m;
int g[101][101];
int visited[101];
 
int dfs(int s)
{
    int i, ret=1;
    visited[s] = 1;
    for(i=1; i<=n; i++) {
        if(g[s][i] && !visited[i])
            ret += dfs(i);
    }
    return ret;
}
 
int main()
{
    scanf("%d%d", &n, &m);
   
    while(m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a][b] = g[b][a] = 1;
    }
        
    printf("%d\n", dfs(1)-1);
 
    return 0;
}
cs


>> 1번 컴퓨터에서 갈 수 있는 컴퓨터의 갯수.



[2583] 영역구하기


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 <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int m, n, k;
int g[105][105];
int dr[]={1, 0, -1, 0};
int dc[]={0, 1, 0, -1};
 
bool safe(int r, int c)
{
    return (0 <= r && r < m) && (0 <= c && c < n); 
}
 
int dfs(int r, int c)
{
    int ret=1;
    g[r][c] = 1;
    for(int k=0; k<4; k++) {
        int nr = r+dr[k];
        int nc = c+dc[k];
        if(safe(nr, nc) && !g[nr][nc])
            ret += dfs(nr, nc);
    }
    return ret;
}
 
int main()
{
    int r, c, ans=0;
    scanf("%d%d%d", &m, &n, &k);
 
    while(k--) {
        int x, y, x2, y2;
        scanf("%d%d%d%d", &x, &y, &x2, &y2);
 
        for(r=y; r<y2; r++)
            for(c=x; c<x2; c++)
                g[r][c] = 1;
    } 
 
 
    vector<int> v;
    for(r=0; r<m; r++) {
        for(c=0; c<n; c++) {
            if(!g[r][c]) {
                ans++;
                v.push_back(dfs(r, c));
            }
        }
    }
    sort(v.begin(), v.end());
    printf("%d\n", ans);
    for(int i=0; i<v.size(); i++)
        printf("%d ", v[i]);
    puts("");
}
cs


>> 영역을 칠하는 것이 핵심인데, 이게 좀 헷갈린다.

>> 영역만 구하면 다음에 할일은 컴퍼넌트 갯수 구하기와 동일하다.



[10451] 순열 사이클


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
#include <stdio.h>
 
int n;
int g[1001][1001];
int visited[1001];
 
void dfs(int s)
{
    int i;
    visited[s] = 1;
 
    for(i=1; i<=n; i++) {
        if(g[s][i] && !visited[i])
            dfs(i);
    }
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int i, j, k;
        int ans=0;
        scanf("%d", &n);
 
        for(i=1; i<=n; i++) {
            scanf("%d", &k);
            g[i][k] = 1;
        }
 
        for(i=1; i<=n; i++) {
            if(!visited[i]) {
                ans++;
                dfs(i);
            }
        }
        
        printf("%d\n", ans);
 
        for(i=1; i<=n; i++) {
            visited[i] = 0;
            for(j=1; j<=n; j++)
                g[i][j] = 0;
        }
    }
    return 0;
}
cs


>> 그래프 모델링 후 컴퍼넌트 구하는 문제.



[]


'Tutoring > PS' 카테고리의 다른 글

Week 6 - BFS (숨박꼭질)  (0) 2018.03.30
Week 5 - BFS  (0) 2018.03.24
Week 4 - BFS  (0) 2018.03.11
Week3 - DFS  (0) 2018.03.07
Week 1 - DFS  (0) 2018.02.20

Week 1 - DFS

Tutoring/PS2018. 2. 20. 00:24

< 180219 >


Week 1 - DFS 


[BOJ/2667] 단지번호 붙이기 (http://boj.kr/2667)


1)


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
#include <cstdio>
#include <algorithm>
 
#define N 101
int n, cnt, a[N][N], s[N];
 
bool safe(int x, int y)
{
    return (0 <= x && x < n) && (0<= y && y < n);
}
 
bool cmp(int a, int b)
{
    return a < b;
}
 
void dfs(int x, int y, int k)
{
    int i, dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
    a[x][y] = k;
    for(i=0; i<4; i++)
        if(safe(x+dx[i], y+dy[i]) && a[x+dx[i]][y+dy[i]]==1 )
            dfs(x+dx[i], y+dy[i], k);
}    
 
void solve(void)
{
    int i, j;
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            if(a[i][j] == 1)
            {
                cnt++;
                dfs(i, j, cnt+1);
            }
 
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            if(a[i][j])
                s[a[i][j]-2]++;
 
    std::sort(s, s+cnt, cmp);
}
 
int main(void)
{
    int i, j;
    scanf("%d", &n);
 
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            scanf("%1d", &a[i][j]);
 
    solve();
 
    printf("%d\n", cnt);
    for(i=0; i<cnt; i++)
        printf("%d\n", s[i]);
 
    return 0;
}
cs





2) 이런식으로도 구현할 수 있다.


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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, cnt, a[101][101];
vector<int> v;
 
bool safe(int x, int y)
{
    return (0 <= x && x < n) && (0<= y && y < n);
}
 
int dfs(int x, int y)
{
    int i, dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
    int ret = 1;
    a[x][y] = 0;
    for(i=0; i<4; i++)
        if(safe(x+dx[i], y+dy[i]) && a[x+dx[i]][y+dy[i]]==1 )
            ret += dfs(x+dx[i], y+dy[i]);
    return ret;
}    
 
void solve(void)
{
    int i, j;
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            if(a[i][j] == 1)
            {
                cnt++;
                v.push_back(dfs(i, j));
            }
        }
    }
 
    sort(v.begin(), v.end());
}
 
int main(void)
{
    int i, j;
    scanf("%d", &n);
 
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            scanf("%1d", &a[i][j]);
 
    solve();
 
    printf("%d\n", cnt);
    for(i=0; i<cnt; i++)
        printf("%d\n", v[i]);
 
}
 
cs


>> dfs() 의 리턴형이 int 이다. 결국 dfs() 호출된 횟수를 리턴하게 된다.

>> vector 를 사용했다.



[BOJ/1012] 유기농 배추 (http://boj.kr/1012)


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
#include <stdio.h>
 
int r, c;
int g[51][51];
int dr[]={1, 0, -1, 0};
int dc[]={0, 1, 0, -1};
 
int safe(int i, int j)
{
    return (0 <= i && i < r) && (0 <= j && j < c);
}
 
void dfs(int r, int c)
{
    int k;
    g[r][c] = 0;
 
    for(k=0; k<4; k++) {
        int nr = r + dr[k];
        int nc = c + dc[k];
        if(safe(nr, nc) && g[nr][nc])
            dfs(nr, nc);
    }
 
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
    
    while(tc--) {
        int i, j, k;
        int ans = 0;
        scanf("%d%d%d", &r, &c, &k);
    
        while(k--) {
            int a, b;
            scanf("%d%d", &a, &b);
            g[a][b] = 1;
        }
                
        for(i=0; i<r; i++) {
            for(j=0; j<c; j++) {
                if(g[i][j]) {
                    ans++;
                    dfs(i, j);
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}
cs


>> 16 : 방문체크 배열을 따로 안만들고, 방문한곳을 0으로 바꿔줌으로써 다시 방문할 수 없도록 하였다.



[BOJ/4963] 섬의 개수 (http://boj.kr/2963)


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
#include <stdio.h>
 
int r, c;
int g[51][51];
int di[]={-1, -1, -1, 0, 0, 1, 1, 1};
int dj[]={-1, 0, 1, -1, 1, -1, 0, 1};
 
int safe(int i, int j)
{
    return (0 <= i && i < r) && (0 <= j && j < c);
}
 
void dfs(int i, int j)
{
    int k;
    g[i][j] = 0;
 
    for(k=0; k<8; k++) {
        int ni = i+di[k];
        int nj = j+dj[k];
        if(safe(ni, nj) && g[ni][nj])
            dfs(ni, nj);
    }
}
 
int main()
{
    while(1) {
        int i, j;
        int ans=0;
        scanf("%d%d", &c, &r);
 
        if(!r && !c) break;
        
        for(i=0; i<r; i++)
            for(j=0; j<c; j++)
                scanf("%d", &g[i][j]);
 
        for(i=0; i<r; i++) {
            for(j=0; j<c; j++) {
                if(g[i][j]) {
                    ans++;
                    dfs(i, j);
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}
cs


>> 위와 같은 유형의 문제. 차이점이라면 8방탐색..!!

'Tutoring > PS' 카테고리의 다른 글

Week 6 - BFS (숨박꼭질)  (0) 2018.03.30
Week 5 - BFS  (0) 2018.03.24
Week 4 - BFS  (0) 2018.03.11
Week3 - DFS  (0) 2018.03.07
Week 2 - DFS  (0) 2018.02.21

티스토리툴바