#문제

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

 

1051번: 숫자 정사각형

N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

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, m;
char board[51][51];
int main(){
    cin>>n>>m;
    
    for(int i=0; i<n; i++){
        cin>>board[i];
    }
    
    int size_max = min(n, m);
    
    int result = 0;
    for(int size=0; size<size_max; size++){
        for(int i=0; i<n-size; i++){
            for(int j=0; j<m-size; j++){
                if(board[i][j]==board[i+size][j])
                    if(board[i][j]==board[i][j+size])
                        if(board[i][j]==board[i+size][j+size])
                            result = max(result, size+1);
            }
        }
    }
    
    cout<<result*result;
    return 0;
}
 cs

##

너무 오랜만에 문제를 풀었다... 다시 기본부터

실수 1. 최대 입력 가능한 n, m의 크기가 50이므로 배열을 [51][51]으로 선언해야함.

실수 2. 1x1사이즈의 정사각형이 만들어질 수 있음을 간과함.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 10552번 :: DOM  (0) 2020.02.25
BOJ 2468번 :: 안전영역  (0) 2020.02.22
BOJ 11403번 :: 경로 찾기  (0) 2020.02.21
BOJ 10026번 :: 적록색약  (0) 2020.02.16
BOJ 2583번 :: 영역 구하기  (0) 2020.02.13

#문제

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

 

10552번: DOM

The first line of input contains three integers N, M and P (1 ≤ N, M ≤ 105, 1 ≤ P ≤ M), the number of pensioners, the number of TV channels and the initial channel displayed on TV. Each of the following N lines contains two integers ai and bi (1 ≤ ai, bi ≤

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
#include <iostream>
using namespace std;
 
int n, m, p;
bool visit[100001];
int hateToFav[100001];
 
int search(int now){
    // 현재 채널을 방문처리. 
    visit[now] = true;
    // 현재 채널을 싫어하는 사람이 바꿀 채널을 next에 저장. 
    int next = hateToFav[now];
    // next==0은 현재 채널을 싫어하는 사람이 없다는 뜻. 
    if( next == 0 ) return 0;
    
    // next 채널에 방문한 적 있다면 앞으로도 사이클을 돌 것.
    // -1을 출력해준다. 
    if( visit[next] ){
        return -1;
    }
    
    // 다음 채널을 기준으로 싫어하는 사람이 채널을 돌리도록 deep하게 탐색. 
    int deep = search(next);
    // 그 다음에 사이클이 발생하면 -1을 출력하고, 사이클이 발생하지 않는다면 채널 변경 횟수 1 추가. 
    return deep==-1?-1:deep+1;
}
 
int main(){
    cin>>n>>m>>p;
    
    for(int i=0; i<n; i++){
        int fav, hate;
        cin>>fav>>hate;
        // 먼저 입력된 사람의 선호(=어린 사람의 선호)
        // 싫어하는 채널이 같은 사람이 여러 명이라면 그 중 가장 먼저 입력된 사람이 채널을 바꾸므로. 
        if( hateToFav[hate]==0 )
            hateToFav[hate] = fav;
    }
    
    cout<<search(p);
    return 0;
}
cs

##

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 1051번 :: 숫자 정사각형  (0) 2020.04.16
BOJ 2468번 :: 안전영역  (0) 2020.02.22
BOJ 11403번 :: 경로 찾기  (0) 2020.02.21
BOJ 10026번 :: 적록색약  (0) 2020.02.16
BOJ 2583번 :: 영역 구하기  (0) 2020.02.13

#문제

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

 

2468번: 안전 영역

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어

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
#include <iostream>
using namespace std;
 
int n;
int area[100][100];
bool visit[100][100];
int d[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
int max_height;
int max_safe=0;
 
void cal(int x, int y, int h){
    visit[x][y] = true;
    
    // 상하좌우로 연결되어있는 안전영역 방문체크. 
    for(int v=0; v<4; v++){
        int newx = x+d[v][0];
        int newy = y+d[v][1];
        // 상하좌우가 영역을 벗어나지 않을 때만 체크. 
        if( 0<=newx&&newx<n&&0<=newy&&newy<n) 
        if( area[newx][newy]>h && !visit[newx][newy] ){
            cal(newx, newy, h);
        }
    }
}
 
int main(){
    cin>>n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>>area[i][j];
            max_height = max(max_height, area[i][j]);
        }
    }
    
    for(int h=0; h<=max_height; h++){
        // 매 h마다 visit배열을 초기화시켜준다. 
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                visit[i][j] = false;
        // 매 번 발생하는 safe_area개수 초기화.
        int safe_area = 0;
        
        // 안전영역을 찾으면 상하좌우 방문체크. 
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if( area[i][j]>h && !visit[i][j] ){
                    safe_area++;
                    cal(i, j, h);
                }
            }
        }
        
        max_safe = max(max_safe, safe_area);
    }
    
    cout<<max_safe<<'\n';
    return 0;
} 
 cs

##

1. 지역의 높이 정보를 입력받으면서 가장 높은 지역의 높이를 max_height에 저장해둔다.

2. 수면의 높이 h를 0 ~ max_height까지 반복하며 발생할 수 있는 안전영역의 개수를 센다.(dfs)

   매 h마다 어느 지역을 방문했는지 표시하는 visit배열을 초기화해주어야한다.

3. 최대 안전영역의 개수를 업데이트 한다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 1051번 :: 숫자 정사각형  (0) 2020.04.16
BOJ 10552번 :: DOM  (0) 2020.02.25
BOJ 11403번 :: 경로 찾기  (0) 2020.02.21
BOJ 10026번 :: 적록색약  (0) 2020.02.16
BOJ 2583번 :: 영역 구하기  (0) 2020.02.13

#문제

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

 

11403번: 경로 찾기

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

#작성 코드

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 <iostream>
using namespace std;
 
int n;
bool graph[101][101];        // 가중치 없는 방향 그래프 
 
int main(){
    /* 정점의 개수 n개 입력 */
    cin>>n;
    /* 그래프의 인접 행렬 입력 */
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>>graph[i][j];
        }
    }
    
    /* n개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력.
    정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1으로, 없으면 0으로. */
    // floyd-warshall 알고리즘 적용.
    for(int k=0; k<n; k++){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if( graph[i][k] && graph[k][j] ){
                    graph[i][j] = true;
                }
            }
        }
    }
    
    // 출력 
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout<<graph[i][j]<<' ';
        }
        cout<<'\n';
    }
    return 0;
}
 cs

2. 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
47
48
49
#include <iostream>
using namespace std;
 
int n;
int graph[100][100];
int path[100][100];
bool visit[100];
 
void search(int i){
    // 정점 i에 연결된 정점들 중 방문하지 않은 정점을 방문. ( n level ) 
    for(int k=0; k<n; k++){
        if( graph[i][k] && !visit[k] ){
            visit[k] = true;        // 방문하지 않은 정점인 k를 방문처리하고 
            search(k);                // k에 연결된 방문하지 않은 정점을 방문. ( n+1 level ) 
        }
    }
}
 
int main(){
    // 입력 
    cin>>n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>>graph[i][j];
        }
    }
    
    // 경로 찾기 
    for(int i=0; i<n; i++){
        fill_n(visit, 100, 0);        // 매 정점 i를 탐색할 때마다 visit배열을 초기화해주어야한다. 
        search(i);
        
        // i정점에서 방문할 수 있는 정점들을 visit배열에서 알아내고, path에 추가. 
        for(int x=0; x<n; x++){
            if( visit[x] ){
                path[i][x] = 1;
            }
        }
    }
    
    // 찾은 경로 출력 
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout<<path[i][j]<<' ';
        }
        cout<<'\n';
    }
    return 0;
} 
 cs

##

N의 최대 크기가 100이기 때문에 O(n^3)의 플로이드 와샬 알고리즘을 사용할 수 있다.

 

* DFS를 이용한 풀이

인덱스 0의 정점에서 (for문){ graph[0][i]가 있으면 인덱스 i를 방문. (재귀){인덱스 i의 정점에서 graph[i][j]가 있으면 인덱스 j를 방문. ...} ... }

시작 정점에서 재귀함수로 들어가기 전에, visit 배열을 초기화시켜주어야한다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 10552번 :: DOM  (0) 2020.02.25
BOJ 2468번 :: 안전영역  (0) 2020.02.22
BOJ 10026번 :: 적록색약  (0) 2020.02.16
BOJ 2583번 :: 영역 구하기  (0) 2020.02.13
BOJ 1743번 :: 음식물 피하기  (0) 2020.02.13

#문제

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

 

10026번: 적록색약

문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), 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
#include <iostream>
using namespace std;
 
int n;
char pic[101][101];
bool visit[101][101];
int d[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
int rgb=0, nonrgb=0;
 
void RGBpeople(int x, int y, char now){
    visit[x][y] = true;
    for(int v=0; v<4; v++){
        int newx = x+d[v][0];
        int newy = y+d[v][1];
        if( 0<=newx&&newx<n && 0<=newy&&newy<n ){
            if( visit[newx][newy]==true ) continue;        // 이미 방문했던 지점은 패스 
            // 현재 탐색중인 색과 상하좌우 위치의 색이 같을때 
            if( now==pic[newx][newy] )
                RGBpeople(newx, newy, now);
        }
    }
}
 
void nonRGBpeople(int x, int y, char now){
    visit[x][y] = true;
    for(int v=0; v<4; v++){
        int newx = x+d[v][0];
        int newy = y+d[v][1];
        if( 0<=newx&&newx<n && 0<=newy&&newy<n ){
            if( visit[newx][newy]==true) continue;        // 방문했던 지점은 패스 
            // 현재 탐색중인 색이 'R' 또는 'G'일 때 
            if( now=='R'||now=='G'){
                if(pic[newx][newy]=='R'){
                    nonRGBpeople(newx, newy, 'R');
                }
                else if(pic[newx][newy]=='G'){
                    nonRGBpeople(newx, newy, 'G');
                }
            }
            // 현재 탐색중인 색이 'B'일 때 
            else{
                // 상하좌우가 현재 탐색중인 색과 같을때 
                if( now==pic[newx][newy] )
                    nonRGBpeople(newx, newy, now);
            }
        }
    }
}
 
int main(){
    /* 그림이 입력으로 주어짐 */
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>pic[i];
    }
 
    /* 적록색약이 아닌 사람이 봤을 때 구역의 수 구하기 */
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if( visit[i][j]==false ){
                rgb++;
                RGBpeople(i, j, pic[i][j]);
            }
        }
    }
    
    /* visit 배열 초기화 */
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            visit[i][j] = false;
        }
    }
    
    /* 적록색약인 사람이 봤을 때 구역의 수 구하기 */
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if( visit[i][j]==false ){
                nonrgb++;
                nonRGBpeople(i, j, pic[i][j]);
            }
        }
    }
    
    cout<<rgb<<' '<<nonrgb<<'\n';
    return 0;
}
 cs

##

적록색약이 아닌 사람이 그림을 볼때, 현재 'B'를 탐색 중일 때 다음 위치의 색이 현재 색과 같아야 탐색한다는 조건을 빠트려서

nonRGBpeople 함수에서 B 탐색 이후에 어느 색이든 무작위로 방문하는 문제가 발생했다.

조건 빠트리지 말자!

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 2468번 :: 안전영역  (0) 2020.02.22
BOJ 11403번 :: 경로 찾기  (0) 2020.02.21
BOJ 2583번 :: 영역 구하기  (0) 2020.02.13
BOJ 1743번 :: 음식물 피하기  (0) 2020.02.13
BOJ 11724번 :: 연결 요소의 개수  (0) 2020.02.12

#문제

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

 

2583번: 영역 구하기

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

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>
#include <algorithm>
using namespace std;
 
int m, n, k;        // 모두 100이하의 자연수 
int paper[101][101];    // (0,0)~(n,m)이 존재하므로 n,m의 최댓값인 100까지는 수용해야한다. 
int area[101*101/2+1];        // [1]~[areaNum]에 저장된다. 
int areaNum=0;
int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; 
int square[100][4];
 
void dfs(int x, int y, int aN){
    paper[x][y] = aN+2;        // 이미 숫자를 센 빈 공간에는 aN+2를 저장해서 다시 찾지 않도록. 
    area[aN]++;
    for(int v=0; v<4; v++){
        int newx = x+d[v][0];
        int newy = y+d[v][1];
        if( 0<=newx&&newx<n&&0<=newy&&newy<m )
        if( paper[newx][newy]==0 ){
            dfs(newx, newy, aN);
        }
    }
}
 
int main(){
    /* m, n, k 입력 */
    cin>>m>>n>>k;
    /* k개의 직사각형 좌하(a, b), 우상단(c, d) 좌표 입력 */
    for(int i=0; i<k; i++){
        int a, b, c, d;
        cin>>a>>b>>c>>d;
        // 직사각형을 1로 마킹해주자. 
        for(int p=a; p<c; p++){
            for(int q=b; q<d; q++){
                paper[p][q]=1;
            }
        }
    }
 
    /* 나눠진 영역의 개수를 세고, 각 영역의 넓이를 계산한다. */
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if( paper[i][j]==0 ){
                areaNum++;
                dfs(i, j, areaNum);
            }
        }
    }
    
    /* 분리되어 나누어지는 영역의 개수 출력 */
    cout<<areaNum<<'\n';
    
    /* 각 영역의 넓이 오름차순으로 정렬하여 빈칸을 사이에 두고 출력 */
    sort(area+1, area+areaNum+1);    // 1번인덱스~areaNum인덱스까지 정렬 
    for(int i=1; i<=areaNum; i++){    // 1번인덱스~areaNum인덱스까지 출력 
        cout<<area[i]<<' ';
    }
    return 0;
}
 
 cs

##

새롭게 탐색할 상하좌우 위치가 범위 내에 존재하는지 체크하고 탐색해야하는것 잊지 말자!

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 11403번 :: 경로 찾기  (0) 2020.02.21
BOJ 10026번 :: 적록색약  (0) 2020.02.16
BOJ 1743번 :: 음식물 피하기  (0) 2020.02.13
BOJ 11724번 :: 연결 요소의 개수  (0) 2020.02.12
BOJ 9466번 :: 텀 프로젝트  (0) 2020.02.12

+ Recent posts

티스토리툴바