#문제

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

 

1743번: 음식물 피하기

문제 코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다.  이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다.  통로에 떨어진 음식물을 피해가기란 쉬운 일이 아

www.acmicpc.net

 

#작성 코드

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
#include <iostream>
using namespace std;
 
/*
1743 음식물 피하기
 
떨어진 음식물 중에 제일 큰 음식물은 피하고 싶다!
 
*/
 
int n, m, k;    // 통로의 세로길이, 가로길이, 음식물 쓰레기 개수
bool trash[101][101];    // [1][1] ~ [n][m] 사용.
bool visit[101][101];
int tmpbunch=0;
int bunch=0;        // 가장 큰 음식물 쓰레기의 크기 저장. 
int d[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
 
void dfs(int x, int y){
    visit[x][y] = true;
    tmpbunch++;        // 현재 [x][y]개수를 tmpbunch에 추가. 
    for(int v=0; v<4; v++){
        int newx = x+d[v][0];
        int newy = y+d[v][1];
        if( 1<=newx&&newx<=n&&1<=newy&&newy<=m ){
            if( trash[newx][newy]==true && visit[newx][newy]==false ){
                visit[newx][newy] = true;
                dfs(newx, newy); 
            }
        }
    }
} 
 
int main(){
    /* 통로의 세로길이, 가로길이, 음식물 쓰레기 개수 입력*/
    cin>>n>>m>>k;
    /* k개의 음식물이 떨어진 좌표 입력 */
    for(int K=0; K<k; K++){
        int x, y;
        cin>>x>>y;
        trash[x][y] = 1;
    }
    
    /* 음식물 중 가장 큰 음식물의 '크기'를 출력 */
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            // 음식물 쓰레기를 찾는다. 
            if( trash[i][j]==true ){
                // 방문한 적 없는 쓰레기라면 그 쓰레기에 연결된 쓰레기 탐색. 
                if( visit[i][j]==true ) continue;
                else{
                    dfs(i, j);    
                }
            }
            bunch = max(bunch, tmpbunch);
            tmpbunch=0;
        }
    }
    cout<<bunch<<'\n';
    return 0;
} 
 cs

##

전엔 이런 문제들을 대부분 bfs로 풀었는데, dfs로 푸는 방법에도 익숙해지는 중...

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 10026번 :: 적록색약  (0) 2020.02.16
BOJ 2583번 :: 영역 구하기  (0) 2020.02.13
BOJ 11724번 :: 연결 요소의 개수  (0) 2020.02.12
BOJ 9466번 :: 텀 프로젝트  (0) 2020.02.12
BOJ 5430번 :: AC  (0) 2020.02.11

#문제

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

 

11724번: 연결 요소의 개수

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

www.acmicpc.net

 

#작성 코드

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>
using namespace std;
 
int n, m;
int graph[1000][1000];
bool visit[1000];
 
void dfs(int now){
    visit[now] = true;        // now에 방문표시. 
    // now의 인접정점들 중 방문하지않은것들에 방문한다. 
    for(int i=0; i<n; i++){
        if( graph[now][i] && !visit[i]){
            // now와 i간의 연결이 존재 && i에 방문한 적 없을때
            dfs(i);
        }
    }
}
 
int main(){
    /* 정점의 개수 n, 간선의 개수 m 입력 */
    cin>>n>>m;
    for(int input=0; input<m; input++){
        int from, to;
        cin>>from>>to;
        // from과 to에 각각 -1을 하는 이유는 나는 인덱스 0부터 사용했기 때문
        // 1번 정점의 인덱스는 0이다. 
        graph[from-1][to-1] = graph[to-1][from-1] = 1;        // 무방향 그래프 설정 
    } 
    
    /* 연결요소 탐색 */
    int cnt=0;
    for(int i=0; i<n; i++){
        if( visit[i] ) continue;
        dfs(i);
        cnt++;
    } 
    cout<<cnt<<'\n';
    return 0;
}
 cs

##

연결 요소의 개수를 구해라 -> 서로 연결되어있는 정점의 그룹이 총 몇개인가?

정점 1부터 n까지 for문을 돌며 선택. 각 정점에 연결된 인접정점들을 돌며 방문표시. 한 시작 정점에 대해 인접정점들 방문표시가 모두 끝났으면 cnt를 1 증가시킨다.(line 35)

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 2583번 :: 영역 구하기  (0) 2020.02.13
BOJ 1743번 :: 음식물 피하기  (0) 2020.02.13
BOJ 9466번 :: 텀 프로젝트  (0) 2020.02.12
BOJ 5430번 :: AC  (0) 2020.02.11
BOJ 3078번 :: 좋은 친구  (0) 2020.02.10

#문제

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

 

9466번: 텀 프로젝트

문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r=

www.acmicpc.net

 

#작성 코드

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 <iostream>
using namespace std;
 
// 모든 학생들은 함께하고싶은 학생 선택해야하고,
// 혼자하고 싶은 학생은 자기 자신만 선택할 수도 있다.
 
int t, n, cnt=0;        // cnt : 사이클에 속하는(팀을 이룬) 정점 개수 
int select[100000];        // [i] : i학생이 누구를 선택했는지 저장. 
bool visit[100000];
bool finished[100000];
 
void dfs(int i){
    visit[i] = true;        // 방문표시
    int next = select[i];
    if( visit[next]==true ){
        // i가 선택한 학생이 방문'했던'  학생일 때
        if( finished[next]==false ){
            // i가 선택한 학생이 아직 사이클에 포함되지 않은 학생일 때
            int tmp=next;
            while( tmp!=i ){
                cnt++;        // 사이클을 형성하는 학생들을 차례로 포함한다. 
                tmp = select[tmp];
            }
            cnt++;        // i 자기 자신을 사이클에 포함시킨다. 
        } 
    }
    else{
        // i가 선택한 학생을 아직 방문하지 않았다면 방문한다. 
        dfs(next);
    }
    finished[i] = true;
}
 
int main(){
    /* 테스트케이스의 개수 T 입력 */
    cin>>t;
    for(int T=0; T<t; T++){
        /* 학생의 수 n입력. 2<=n<=100,000 */
        cin>>n;
        // 각 학생이 선택한 학생을 입력한다. 
        for(int i=0; i<n; i++){
            int x; cin>>x;
            select[i] = x-1;        // 입력은 인덱스 1부터 시작하도록 들어오므로. 
        }
        // visit, team 배열 초기화 
        fill(visit, visit+n, false);
        fill(finished, finished+n, false);
        /* 어느 프로젝트 팀에도 속하지 않는 학생 수를 구한다. */
        cnt=0; 
        for(int i=0; i<n; i++){
            if( visit[i]==false )
                dfs(i);
        }
        cout<<n-cnt<<'\n';
    }
    return 0;
}
 cs

##

학생들간의 선택이 사이클을 이룬다면, 그 사이클을 이루는 학생들은 한 팀을 이뤘다고 할 수 있다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 1743번 :: 음식물 피하기  (0) 2020.02.13
BOJ 11724번 :: 연결 요소의 개수  (0) 2020.02.12
BOJ 5430번 :: AC  (0) 2020.02.11
BOJ 3078번 :: 좋은 친구  (0) 2020.02.10
BOJ 1182번 :: 부분수열의 합  (0) 2020.02.06

#문제

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

 

5430번: AC

문제 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다.

www.acmicpc.net

 

#작성 코드

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
#include <iostream>
#include <string>
#include <deque>
using namespace std;
 
deque<int> arr;
 
int main(){
    /* 테스트케이스의 개수 t (t<=100) */
    int t; cin>>t;
    for(int tc=1; tc<=t; tc++){
        bool error = false;                    // 에러 발생 여부 
        /* 수행할 함수 p가 주어짐. (1<=p의 길이<=100000)
        // R: 역순으로 변환 , D: 첫 번째 숫자를 버린다. */
        string func; cin>>func;
        /* 배열에 들어 있는 수의 개수 n이 주어짐 (0<=n<=100000) */
        int n; cin>>n;
        /* 배열의 원소 입력 ex) [1,2,3] */
        arr.erase(arr.begin(), arr.end());
        string arrinput; cin>>arrinput;
        // deque<int> arr에 숫자만 저장.
        int num=0;
        if( n!=0 ){
            for(int i=1; i<arrinput.length(); i++){
                if( '0'<=arrinput[i]&&arrinput[i]<='9'){
                    num = num*10 + arrinput[i]-'0';
                }
                else{
                    arr.push_back(num);
                    num=0;
                }
            }
        }
        
        /* 함수를 수행 */
        bool reverse = false;    // 역순으로 처리할지? true/false 
        // 함수를 차례대로 하나씩 수행한다. 
        for(int i=0; i<func.length(); i++){
            // reverse 반전. 
            if( func[i]=='R' ){
                if(reverse==false) reverse=true;
                else reverse=false;
            }
            else if( func[i]=='D' ){
                if( arr.empty() ){ // 에러 발생을 표시하고 함수 실행 종료
                    error=true;
                    break;
               }
                if( !reverse ){
                    // 앞에서 하나 제거 
                    arr.pop_front();
                }
                else{
                    // 뒤에서 하나 제거
                    arr.pop_back();
                }
            }
        }
        
        /* 함수 수행 결과를 출력한다. */
        // 에러가 발생한 경우에는 error를 출력한다. 
        // 에러발생 : 모든 연산 후에 []내에 아무것도 없을 때 == deque가 비게 되면
        if( error ){
            cout<<"error\n";
            continue;
        }
        
        if( !reverse ){
            // 순서대로 출력한다.
            cout<<'[';
            for(int i=0; i<arr.size(); i++){
                cout<<arr[i];
                if( i!=arr.size()-1 ){
                    cout<<',';
                }
            }
            cout<<']'<<'\n';
        }
        else{
            // 역순으로 출력한다. 
            cout<<'[';
            for(int i=arr.size()-1; i>=0; i--){
                cout<<arr[i];
                if( i!=0 ){
                    cout<<',';
                }
            }
            cout<<']'<<'\n';
        }
    } 
    return 0; 
}
 cs

##

49, 53번째 줄에서 pop연산 후에 deque가 비면 break로 함수 실행부를 빠져나가고 에러 출력으로 넘어가도록 프로그램을 짰었는데,

그런 경우는 아무 것도 없는 deque에서 pop연산을 시도한 것이 아니기 때문에 에러를 출력하면 안된다.

에러는 아무 것도 없는 deque에서 pop연산을 시도했을 때 발생한다.

함수를 하나 수행할 때마다 deque가 비었을 때 D(pop연산)를 수행하려고 하는지 체크하고, 에러가 발생하면 에러 발생을 체크하고 그 이후의 함수는 수행하지 않는다.(수행해도 아무런 효과가 없기 때문)

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 11724번 :: 연결 요소의 개수  (0) 2020.02.12
BOJ 9466번 :: 텀 프로젝트  (0) 2020.02.12
BOJ 3078번 :: 좋은 친구  (0) 2020.02.10
BOJ 1182번 :: 부분수열의 합  (0) 2020.02.06
BOJ 2503번 :: 숫자 야구  (0) 2020.02.06

#문제

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

 

1182번: 부분수열의 합

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

 

#작성 코드

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
#include <iostream>
using namespace std;
 
int n, s, num[20], cnt=0;
 
void partsum(int idx, int sum){
    if( idx>=n ) return;
    int tmp = sum + num[idx];
    if( tmp == s ) cnt++;
    partsum(idx+1, sum);        // num[idx]를 포함하지 않는 경우 
    partsum(idx+1, tmp);        // num[idx]를 포함하는 경우 
}
 
int main(){
    // input 
    cin>>n>>s;
    for(int i=0; i<n; i++){
        cin>>num[i];
    }
    
    // solve
    // 1. 원소가 1개 ~ n개인 부분집합을 구한다.
    // 2. 그 부분집합의 원소의 합이 s이면 cnt를 1 증가시킨다.
    partsum(0, 0);
    
    // 3. cnt를 출력한다.
    cout<<cnt<<'\n';
    return 0;
}
 cs
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 <iostream>
using namespace std;
 
int n, s, cnt=0;
int nums[20];
 
int main(){
    cin>>n>>s;
    for(int i=0; i<n; i++){
        cin>>nums[i];
    }
    
    for(int bi=1; bi<(1<<n); bi++){
        int sum=0;
        // n이 5, bi가 10010이라면 우측에서부터 2번째, 5번째 인덱스 값을 포함한다는 뜻.
        // bi는 1 ~ 2^5 -1 이므로
        // bi의 개수는 원소가 5개인 집합의 부분집합 중 공집합을 제외한 개수가 된다. 
        for(int digit=0; digit<n; digit++){
            if( bi&(1<<digit) ){
                sum = sum+nums[digit];
            }
        }
        if( sum==s ) cnt++; 
    }
    
    cout<<cnt<<'\n';
    return 0;
}
 cs

##

1. 재귀를 이용한 방법

2. 비트마스킹을 이용한 방법

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 5430번 :: AC  (0) 2020.02.11
BOJ 3078번 :: 좋은 친구  (0) 2020.02.10
BOJ 2503번 :: 숫자 야구  (0) 2020.02.06
BOJ 10448번 :: 유레카 이론  (0) 2020.02.04
BOJ 3085번 :: 사탕 게임  (0) 2020.02.04

+ Recent posts

티스토리툴바