반응형

문제출처

https://programmers.co.kr/learn/courses/30/lessons/42842


문제를 읽으면 빨간색은 갈색으로 둘러쌓여있다고 한다. 즉 카펫의 가로,세로가 3이상이라는 뜻이다. 또한 빨간타일을 구할때는 위,아래 row와 왼쪽,오른쪽 col을 제외한 크기를 곱하면 빨간타일의 갯수가 나온다.


소스코드

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
#include <string>
#include <vector>
#include <math.h>
using namespace std;
 
vector<int> solution(int brown, int red) {
    vector<int> answer;
    int sum=brown+red;
    int limit=(int)sqrt(sum);
    
    for(int i=3; i<=limit; i++)
    {
        if(sum % i ==0)
        {
            int tmp = sum/i;
            //전체 카펫 위,아래 row 왼쪽,오른쪽 col을 제외하고 곱하면 red타일의 갯수가 나온다.
            if((tmp-2) * (i-2) == red)
            {
                answer.push_back(tmp);
                answer.push_back(i);
                break;
            }
        }
    }
    return answer;
}
cs




반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[카카오 2019] 코딩테스트 - 오픈채팅방  (0) 2019.01.03
[카카오 2019] 코딩테스트 - 실패율  (0) 2019.01.03
[프로그래머스 43162] 네트워크  (0) 2019.01.01
[BOJ 6603] 로또  (0) 2018.12.31
[BOJ 2667] 단지번호붙이기  (0) 2018.12.31
반응형

문제 출처

https://programmers.co.kr/learn/courses/30/lessons/43162


dfs로 전체 탐색을 하면서 순회가 끝나면 answer값을 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
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool visit[200];
 
void dfs(int start, vector<vector<int>> &computers, int n) {
    visit[start]=1;
    for(int i=0; i<n; i++)
    {
        if(!visit[i] && computers[start][i])
            dfs(i, computers, n);
    }
    
}
 
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    for(int i=0; i<n; i++)
    {
        if(!visit[i])
        {
            answer++;
            dfs(i, computers, n);
        }
    }
    return answer;
}
 
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[카카오 2019] 코딩테스트 - 실패율  (0) 2019.01.03
[프로그래머스 42842] 카펫  (2) 2019.01.02
[BOJ 6603] 로또  (0) 2018.12.31
[BOJ 2667] 단지번호붙이기  (0) 2018.12.31
[Programmers 43165] 타겟넘버  (0) 2018.12.31
반응형

문제출처

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


간단한 dfs문제이다. xcode에 에러가 있어서 무슨 문제인가 계속 살펴봤는데 그냥 xcode 문제....

dfs호출시 시작 index와 depth를 인자로 넘겨줘서 끝까지 탐색하는 방법이다.


소스코드

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
//
//  main.cpp
//  BOJ_6603
//
//  Created by sw on 31/12/2018.
//  Copyright © 2018 sw. All rights reserved.
//
#include <stdio.h>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int MAX = 13;
int k;
int num[MAX];
int result[MAX];
 
void dfs(int start, int depth) {
    if(depth == 6)
    {
        for(int i=0; i<depth; i++)
        {
            printf("%d ", result[i]);
        }
        printf("\n");
        
        return;
    }
    
    for(int i=start; i<k; i++)
    {
        result[depth]=num[i];
        dfs(i+1, depth+1);
    }
}
int main(int argc, const char * argv[]) {
    
    while(true)
    {
        scanf("%d", &k);
        if(k==0){
            printf("\n");
            break;
        }
        for(int i=0; i<k; i++)
        {
            scanf("%d", &num[i]);
        }
        dfs(0,0);
        printf("\n");
    }
    return 0;
}
 
cs




반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[프로그래머스 42842] 카펫  (2) 2019.01.02
[프로그래머스 43162] 네트워크  (0) 2019.01.01
[BOJ 2667] 단지번호붙이기  (0) 2018.12.31
[Programmers 43165] 타겟넘버  (0) 2018.12.31
[BOJ 2644] 촌수계산  (0) 2018.12.31
반응형

문제출처

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


DFS로 풀이한 문제 따로 visit배열을 사용하지 않고 dfs를 호출할 때 이미 방문한 곳은 값을 0으로 할당합니다. 때문에 map이 1인 경우만 탐색하면 되며 한개의 단지를 구한 후 dfs가 재호출될때 기존의 단지는 map상에 0이므로 재방문을 하지 않습니다. 


소스코드

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
//
//  main.cpp
//  BOJ_2667
//
//  Created by sw on 31/12/2018.
//  Copyright © 2018 sw. All rights reserved.
//
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 25
 
using namespace std;
 
int n, cnt;
vector<int> section;
int map[MAX][MAX];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
 
void init() {
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
        {
            int tmp;
            scanf("%1d", &tmp);
            map[i][j]=tmp;
        }
}
 
void dfs(int x, int y) {
    map[x][y]=0;
    cnt++;
    
    for(int i=0; i<4; i++)
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        
        if(nx>=0 && ny>=0 && nx<n && ny<n && map[nx][ny])
            dfs(nx, ny);
    }
}
 
int main(int argc, const char * argv[]) {
    init();
    
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(map[i][j])
            {
                cnt=0;
                dfs(i, j);
                section.push_back(cnt);
            }
        }
    }
    
    int len = section.size();
    printf("%d\n", len);
    
    sort(section.begin(), section.end());
    for(int i=0; i<len; i++)
        printf("%d\n", section.at(i));
    
    return 0;
}
 
cs



반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[프로그래머스 43162] 네트워크  (0) 2019.01.01
[BOJ 6603] 로또  (0) 2018.12.31
[Programmers 43165] 타겟넘버  (0) 2018.12.31
[BOJ 2644] 촌수계산  (0) 2018.12.31
[BOJ 2606] 바이러스  (0) 2018.12.28

+ Recent posts

티스토리툴바