반응형

[c언어와의 호환성]

- C 언어의 문법 체계 계승

 

 

[입출력]

- 출력

std 이름 공간에 선언된 std::cout 사용

1
2
3
4
5
6
#include<iostream>
 
int main(void) {
    std::cout << "HelloWorld!\n";
    return 0;
}
cs

<< 연산자

-> 스트림 삽입 연산자(stream insertion operator)

-> c++ 기본 산술 시프트 연산자 <<가 <iostream> 헤더 파일에 삽입 연산자로 재정의됨

-> 오른쪽 피연산자를 왼쪽 스트림 객체에 삽입

-> cout 객체에 연결된 화면에 출력

-> 연속된 << 연산자로 여러 값 출력 가능 : std::cout << a << b << c;

 

- 입력

std 이름 공간에 선언된 std::cin 사용

1
2
3
4
5
6
7
#include<iostream>
 
int main(void) {
    int key;
    std::cin >> key;
    return 0;
}
cs

 

 

>> 연산자

-> 스트림 추출 연산자(stream extraction operator)

-> c++ 산술 시프트 연산자 >>가 <iostream> 헤더 파일에 스트림 추출 연산자로 재정의됨

-> 입력 스트림에서 값을 읽어 변수에 저장

-> 연속된 >> 연산자로 여러 값 입력 가능 : std::cin>>a>>b>>c;

 

 

[namespace]

- 변수명 등 이름 충돌이 발생하는 경우 해결에 많은 시간이 필요하다

- 여러 명이 서로 나누어 프로젝트를 개발하는 경우

- 오픈 소스 혹은 다른 사람이 작성한 코드를 가져와서 컴파일 하거나 링크하는 경우

 

namespace 키워드

개발자가 자신만의 이름 공간을 생성해서 다른 이름공간과 구분하여 충돌 해결

1
2
3
4
5
6
7
8
9
10
#include<iostream>
 
namespace my {
    int myVal = 10;
}
 
int main(void) {
    std::cout << my::myVal;
    return 0;
}
cs

 

using 키워드를 사용하면 ~ :: 를 생략할 수 있음 (using namespace std;  -> std:: 생략하고 바로 cout 사용 가능)

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;
namespace my {
    int myVal = 10;
}
 
 
int main(void) {
 
    using namespace my;
    cout <<myVal;
    return 0;
cs

 

 

[객체 지향 개념 도입]

- 캡슐화, 상속, 다형성
- 재사용을 통해 생산성 향상, 큰 규모의 sw의 작성, 유지보수 용이

 

[함수 오버로딩(function overlading)]

- 매개 변수의 개수나 타입이 다른 동일한 이름의 함수들 선언

 

[디폴트 매개 변수(default parameter)]

- 매개 변수에 디폴트 값이 전달되도록 함수 선언

 

[참조와 참조 변수(reference)]

- 하나의 변수에 별명을 사용하는 참조 변수 도입

 

[call-by-address, call-by-reference, call-by-value]

 

[new/delete 연산자]

- 동적 메모리 할당/해체

 

[연산자 재정의]

- 기존 C++ 연산자에 새로운 연산 정의

 

[제네릭 함수와 클래스]

- 데이터 타입에 의존하지 않고 일반화시킨 함수나 클래스 작성 가능

 

[캡슐화]

- 데이터를 캡슐로 싸서 외부의 접근으로부터 보호

- class에서 접근 지정자로 표현한다

 

[클래스와 객체]

- 클래스: 객체를 만드는 템플릿

- 객체(object) : 클래스를 통해서 생겨난 실체

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
using namespace std;
 
class Circle {
private// 캡슐화
    int radius;
public:
    Circle(int r) {
        radius = r;
    }
    double getArea() {
        return 3.14 * radius * radius;
    }
};
 
int main(void) {
    Circle obj(3); //객체 생성
    cout << obj.getArea();
 
    return 0;
}
cs

 

 

[객체 지향 상속(Inheritance)]

- 자식이 부모의 유전자를 물려 받는 것

[C++ 상속]

-기존 클래스를 재사용 또는 확장하여 새로운 클래스를 작성하는 것

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;
 
class animal {
public:
    void breathe() {
        cout << "숨쉬기" << endl;
    }
};
 
class pigeon : public animal { //animal 상속
public:
    void fly() {
        cout << "날다" << endl;
    }
};
class monkey : public animal { //animal 상속
public:
    void walk(){
        cout << "걷는다" << endl;
    }
};
 
int main(void) {
    pigeon p;
    p.fly();
    monkey m;
    m.walk();
 
    return 0;
}
cs

[다형성(Polymorphism)]

- 서로 다른 객체가 동일한 메시지에 대해 다른 방법으로 응답할 수 있는 기능

- 연산자 중복, 함수 중복, 함수 오버라이딩(overriding)

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
#include<iostream>
using namespace std;
 
class animal {
public:
    void move() {
        cout << "움직인다" << endl;
    }
};
 
class pigeon : public animal { //animal 상속
public:
    void move() {
        cout << "날아서 움직인다" << endl;
    }
};
 
class monkey : public animal { //animal 상속
public:
    void move() {
        cout << "걸어서 움직인다" << endl;
    }
};
 
int main(void) {
    pigeon p;
    p.move();
    monkey m;
    m.move();
 
    return 0;
}
cs

 

[소프트웨어 생산성 향상]

- 소프트웨어의 생명 주기 단축 문제 해결 필요

- 기 작성된 코드의 재사용 필요

- C++ 클래스 상속 및 객체 재사용으로 해결

 

[실세계에 대한 쉬운 모델링]

- 실세계는 객체로 구성된 세계이다.

- 객체를 중심으로 하는 객체 지향 언어를 사용하면 쉽게 실세계를 모델링할 수 있다.

 

[절자치향 vs 객체지향 차이]

- 절차 지향

실행하고자 하는 절차대로 일련의 명령어 나열

흐름도를 설계하고 흐름도에 따라 프로그램 작성

- 객체 지향

객체들을 정의하고, 객체들의 상호 관계, 상호 작용으로 구현

 

[제네릭 함수(generic function)]

- 동일한 프로그램 코드에 다양한 데이터 타입을 적용할 수 있게 일반화시킨 함수

1
2
3
4
5
6
7
8
9
10
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}
void swap(double& a, double& b) {
    double temp = a;
    a = b;
    b = temp;
}
cs

위 코드는 함수 오버로딩(재정의)를 통해 같은 코드를 타입만 달리하여 구현하였는데 이는 너무 비효율적이다. 이를 해결하기 위해 다음과 같이 제네릭 함수를 사용한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;
 
template<class T> //템플릿 선언 및 제네릭 타임 T 선언
void newSwap(T& a, T& b) {
    int temp = a;
    a = b;
    b = temp;
}
int main(void) {
    int a = 10;
    int b = 20;
    newSwap(a, b); //제네릭 타입 T에 int를 구체화 시켜 함수를 생성 후 호출
    cout << a << ", " << b << endl;
 
    return 0;
}
cs

 

[제네릭 클래스(generic class)]

- 동일한 프로그램 코드에 다양한 데이터 타입을 적용할 수 있게 일반화시킨 클래스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class calulator {
public:
    int mul(int a, int b) {
        return a * b;
    }
    int div(int a, int b) {
        return a / b;
    }
    int sub(int a, int b) {
        return a - b;
    }
    int add(int a, int b) {
        return a + b;
    }
};
 
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
#include<iostream>
using namespace std;
 
template<typename T>//제네릭 클래스 선언
class calulator {
public:
    T mul(T a, T b) {
        return a * b;
    }
    T div(T a, T b) {
        return a / b;
    }
    T sub(T a, T b) {
        return a - b;
    }
    T add(T a, T b) {
        return a + b;
    }
};
 
int main(void) {
    calulator<double> c; //제네릭 클래스를 double로 구체화해서 객체 생성
    cout << c.mul(2.33.4);
    return 0;
}
cs

 

[C++ 프로그램 개발 과정]

 

1. hello.cpp 소스 파일 작성

2. 컴파일 -> 목적 파일 (hello.obj) 생성
3. 링킹 -> c++ 라이브러리, 여러 목적 파일을 묶어서 실행 파일로 만든다

4. 로더 -> 실행 파일을 메모리에 적재하고 실행시킨다.

 

c++ STL 라이브러리

- 제네릭 프로그래밍을 지원하기 위한 템플릿 라이브러리

- vector, queue, stack... 등

 

 

 

반응형
반응형

문제 링크: https://www.acmicpc.net/problem/19237

 

19237번: 어른 상어

첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미

www.acmicpc.net

<문제 풀이> BFS
이문제는 상어의 방향 정보를 클래스로 묶어서 관리하면 간단하게 해결할 수 있습니다.

그런데 주의할 점은 상어가 이동할 때 여러 상어가 겹치는 부분을 처리해야 하는데 이때 상어를 한 마리씩 이동시킬 때 바로 이동 상태를 맵에 반영하는 게 아니라 임시 큐를 하나 생성해서 임시로 이동시킨 후 번호가 낮은 상어만 맵에 반영해야 합니다.

그리고 또 주의할 점 하나는 시간이 1000초 일 때 상어가 2마리 이상이면 -1을 리턴해야합니다.

<C++ 소스 코드>

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include<iostream>
#include<queue>
#include<utility>
#include<algorithm>
using namespace std;
 
#define X first
#define Y second
 
#define NUM first
#define SMELL second
 
class shark {
public:
    int curDir;
    int nextDir[5][5];
    void del() {
        curDir = -1;
    }
    bool exist() {
        return curDir != -1;
    }
    
};
shark info[401];
int N, M, K;
int board[20][20];
pair<intint> visited[20][20];
queue<pair<intint > > Q;
const int dx[5= {0-1100};
const int dy[5= {00 , 0-11};
int tot_shark;
 
void decreaseSMELL() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visited[i][j].SMELL && !board[i][j]) {
                visited[i][j].SMELL--;
            }
            
        }
    }
}
 
int bfs() {
    int t = 0;
    while (!Q.empty()) {
        int Q_size = Q.size();
        queue<pair<intint> > tempQ; //임시로 다음 상어를 이동 시킴
        queue<int> num; //임시로 이동 시킨 상어의 번호
    
        for (int i = 0; i < Q_size; i++) {
            auto cur = Q.front(); Q.pop();
            if (!info[board[cur.X][cur.Y]].exist())continue;
            bool flag = false//냄새가 없는 곳을 찾으면 true
            for (int dir = 1; dir <= 4; dir++) {
                shark s = info[board[cur.X][cur.Y]];
                int nx = cur.X + dx[s.nextDir[s.curDir][dir]];
                int ny = cur.Y + dy[s.nextDir[s.curDir][dir]];
                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if (visited[nx][ny].SMELL)continue;
                Q.push({ nx, ny });
                tempQ.push({ nx, ny });
                num.push(board[cur.X][cur.Y]);
                info[board[cur.X][cur.Y]].curDir = s.nextDir[s.curDir][dir];
                board[cur.X][cur.Y] = 0;
                flag = true;
                break;
            }
            if (!flag) { // 만약 냄새가 없는 곳이 없으면 자기 냄새가 있는 공간을 찾아서 이동
                for (int dir = 1; dir <= 4; dir++) {
                    shark s = info[board[cur.X][cur.Y]];
                    int nx = cur.X + dx[s.nextDir[s.curDir][dir]];
                    int ny = cur.Y + dy[s.nextDir[s.curDir][dir]];
                    if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                    if (visited[nx][ny].NUM == visited[cur.X][cur.Y].NUM) {
                        tempQ.push({ nx, ny });
                        Q.push({ nx, ny });
                        num.push(board[cur.X][cur.Y]);
                        info[board[cur.X][cur.Y]].curDir = s.nextDir[s.curDir][dir];
                        board[cur.X][cur.Y] = 0;
                        flag = true;
                        break;
                    }
                }
            }
        }
        while (!tempQ.empty()) {
            auto cur = tempQ.front(); tempQ.pop();
            int n = num.front(); num.pop();
            if (board[cur.X][cur.Y]) { //상어가 겹치면
                if (n < board[cur.X][cur.Y]) { // 더 작은 번호의 상어만 살아 남는다
                    info[board[cur.X][cur.Y]].del();
                    board[cur.X][cur.Y] = n;
                    visited[cur.X][cur.Y].SMELL = K;
                    visited[cur.X][cur.Y].NUM = n;
                    
                } 
                tot_shark--//상어 한 마리 죽이기
            }
            else {
                board[cur.X][cur.Y] = n;
                visited[cur.X][cur.Y].SMELL = K;
                visited[cur.X][cur.Y].NUM = n;
            }
        }
        decreaseSMELL();
        t++;
        if (tot_shark == 1return t;
        if (t >= 1000return -1;
     
    }
}
 
 
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
            if (board[i][j] != 0) {
                visited[i][j].NUM = board[i][j];
                visited[i][j].SMELL = K;
                Q.push({ i, j });
                tot_shark++;
            }
        }
    }
    for (int i = 1; i <= M; i++) {
        cin >> info[i].curDir;
    }
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= 4; j++) {
            cin >> info[i].nextDir[j][1];
            cin >> info[i].nextDir[j][2];
            cin >> info[i].nextDir[j][3];
            cin >> info[i].nextDir[j][4];
        }
    }
    info[0].del();
    cout<<bfs();
    return 0;
}
cs

 

반응형

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 1026번] 보물  (0) 2022.08.01
[백준 1932번] 정수 삼각형  (0) 2022.05.06
[백준 19236번] 청소년 상어  (0) 2022.04.03
[백준 16236번] 아기 상어  (0) 2022.03.30
[백준 17142번] 연구소 3  (0) 2022.03.30
반응형

문제 링크: https://www.acmicpc.net/problem/19236

 

19236번: 청소년 상어

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는

www.acmicpc.net

<문제 풀이> 백 트랙킹

이 문제는 백트래킹을 할 때 상태 정보 백업 및 복원이 가장 핵심입니다.

상어를 1칸 이동, 2칸 이동, 3칸 이동시키고 각각에 대해서 재귀 호출할 때 재귀 호출 전에 백업, 호출 후 복원을 하면 되고, 물고기들이 이동하는 건 클래스로 좌표와 방향을 저장해 두고 1번부터 16번까지 단순히 움직이면 됩니다.

 

이때 주의할 점은 상어는 물고기가 있는 칸만 이동할 수 있습니다.
(2칸에 물고기가 없다고 끝내면 안 되고 3칸도 이동해 보아야 한다.)

 

 

 

<C++ 소스 코드>

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include<iostream>
#include<algorithm>
using namespace std;
 
#define SHARK -1
#define EMPTY -2
class pos {
public:
    int x, y, dir;
    void rotate() {
        dir++;
        if (dir == 9) dir = 1;
 
    }
    void del() {
        x = -1; y = -1; dir = -1;
    }
    bool exist() {
        if (x == -1 && y == -1 && dir == -1return false;
        else return true;
    }
};
 
const int dx[9= {0-1-101110-1};
const int dy[9= {00-1-1-10111};
 
pos info[17]; //1~16번 좌표 방향 정보
int board[4][4];
pos shark; //현재 상어 상태
int res = 0;
void move() {
    for (int i = 1; i <= 16; i++) {
        if (!info[i].exist()) continue;
        int startDir = info[i].dir;
        while (true) {
            int nx = info[i].x + dx[info[i].dir];
            int ny = info[i].y + dy[info[i].dir];
            int next = board[nx][ny];
            if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4 || board[nx][ny] == SHARK) {
                info[i].rotate();
                if (startDir == info[i].dir)break;
                continue;
            }
            if (board[nx][ny] == EMPTY) {
                board[nx][ny] = i;
                board[info[i].x][info[i].y] = EMPTY;
                info[i].x = nx;
                info[i].y = ny;
            }
            else {
                swap(board[info[i].x][info[i].y], board[nx][ny]);
                swap(info[i], info[next]);
                swap(info[i].dir, info[next].dir);
            }
            break;
        }
    }
}
 
/*백트랙킹 상태 정보 백업용*/
void backupBoard(int des[4][4], int src[4][4]) {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            des[i][j] = src[i][j];
        }
    }
}
void backupInfo(pos des[17], pos src[17]) {
    for (int i = 0; i < 17; i++) {
        des[i] = src[i];
    }
}
 
 
void solve(int sum) {
    move();
    int cx = shark.x;
    int cy = shark.y;
    int dir = shark.dir;
 
    for (int k = 1; k <= 3; k++) {
        int nx = cx + dx[dir] * k;
        int ny = cy + dy[dir] * k;
        if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4return;
        if (board[nx][ny] == EMPTY) continue;
        int tempBoard[4][4];
        pos tempInfo[17];
        backupBoard(tempBoard, board);
        backupInfo(tempInfo, info);
        shark.x = nx;
        shark.y = ny;
        int num = board[nx][ny];
        res = max(res, sum + num);
        shark.dir = info[num].dir;
        board[nx][ny] = SHARK;
        board[cx][cy] = EMPTY;
        info[num].del();
 
        solve(sum + num);
        
        shark.x = cx;
        shark.y = cy;
        shark.dir = dir;
        backupBoard(board, tempBoard);
        backupInfo(info, tempInfo);
    }    
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            int a, b;
            cin >> a >> b;
            info[a].dir = b;
            info[a].x = i;
            info[a].y = j;
            board[i][j] = a;
        }
    }
 
    shark.x = 0;
    shark.y = 0;
    shark.dir = info[board[0][0]].dir;
 
    info[board[0][0]].del();
    int num  = board[0][0];
    board[0][0= SHARK;
    solve(num);
    cout << res;
    
    return 0;
}
cs

 

반응형
반응형

문제 링크: https://www.acmicpc.net/problem/16236

 

16236번: 아기 상어

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가

www.acmicpc.net

<문제 풀이> BFS, 우선순위 큐, 정렬

BFS를 이용해서 현재 아기 상어가 있는 위치에서부터 아기 상어가 먹을 수 있는 상어들의 위치까지 최단거리를 구하고
먹을 수 있는 상어의 좌표를 우선순위 큐에 넣습니다.
이때 우선순위 큐의 정렬 기준은 거리가 짧은 순, 같다면 X좌표가 작은 순, 같다면 Y좌표가 작은 순입니다.

 

이제 아기 상어의 위치를 우선순위 큐에서 꺼낸 좌표로 갱신하고 그 위치까지의 거리를 결과 값에 저장하면 됩니다(최단 거리가 곧 걸린 시간)

 

위를 상어가 모두 없어질 때까지, 우선순위 큐의 사이즈가 0이 될 때까지 반복하면 됩니다.(상어는 있는데 아기 상어의 크기가 작아서 못 먹는 경우가 있을 수 있다)

 

 

<C++ 소스 코드> 

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
94
95
96
97
98
99
#include<iostream>
#include<utility>
#include<queue>
#include<algorithm>
using namespace std;
 
#define X first
#define Y second
 
int N;
 
int board[20][20];
int visited[20][20];
int cnt;
int sharkSize = 2;
const int dx[4= { -1001 };
const int dy[4= { 0-110 };
 
struct cmp {
    bool operator()(pair<intint >& a, pair<intint>& b) {
        if (visited[a.X][a.Y] > visited[b.X][b.Y]) return true//거리 순
        else if (visited[a.X][a.Y] == visited[b.X][b.Y]) {
            if (a.X > b.X) return true// 위쪽 먼저
            else if (a.X == b.X) return a.Y > b.Y; // 왼쪽 먼저
            else return false;
        }
        else return false;
    }
};
queue<pair<intint> > Q;
priority_queue < pair<intint>vector<pair<intint> >, cmp >pq;
 
 
void bfs() {
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if (visited[nx][ny] != -1continue;
            if (board[nx][ny] != 0 && board[nx][ny] > sharkSize)continue//자신 보다 큰 물고기가 있는 칸은 지나갈 수 없다
            
            if (board[nx][ny] == sharkSize || board[nx][ny] == 0) {//크기가 같거나 빈칸이면 그냥 지나간다.
                Q.push({ nx, ny });
                visited[nx][ny] = visited[cur.X][cur.Y] + 1;
            }
            else { // 크기가 작은 물고기가 있으면
                Q.push({ nx, ny });
                visited[nx][ny] = visited[cur.X][cur.Y] + 1;
                pq.push({ nx, ny });
            }
        }
    }
}
int solve() {
    int ret = 0;
    int ate = 0;
    while (cnt) {
        pq = {}; // init 
        fill(&visited[0][0], &visited[19][20], -1);
 
        pair<intint> start = Q.front();
        visited[start.X][start.Y] = 0;
        bfs();
        if (pq.size() == 0break//먹을 수 있는 물고기가 없을 때
 
        auto target = pq.top();
        board[start.X][start.Y] = 0;
        board[target.X][target.Y] = 9;
        ret += visited[target.X][target.Y];
        Q.push({ target.X, target.Y });
        ate++;
        if (ate == sharkSize) {
            ate = 0;
            sharkSize++;
        }
        cnt--;
    }
    return ret;
 
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
            if (board[i][j] >= 1 && board[i][j] <= 6) cnt++;
            else if (board[i][j] == 9) Q.push({ i, j });
        }
    }
    cout << solve();
 
    return 0;
}
cs
반응형
반응형

문제 링크: https://www.acmicpc.net/problem/17142

 

17142번: 연구소 3

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고

www.acmicpc.net

<문제 풀이> 조합, BFS
이 문제는 두 가지만 조심하면 되는데

 

첫 번째는 "활성 바이러스로 인해 비활성 바이러스가 활성 바이러스로 바뀔 때 0초가 걸린다"입니다.

이 경우에는 활성 바이러스를 기준으로 BFS를 하다가 비활성 바이러스를 만나면 따로 바이러스라고 체크해주고 나중에 걸린 시간을 갱신할 때 이 부분은 스킵하면 됩니다.

 

두 번째는 조합 알고리즘입니다.

10Cm의 조합 알고리즘을 작성해야 하는데 실수로 틀린 알고리즘을 작성해서 시간이 더 오래 걸릴 수도 있습니다.

아래 문제를 풀어보시면 도움이 됩니다.

[조합 문제]
https://www.acmicpc.net/problem/15663

 

15663번: N과 M (9)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

 

 

<C++ 소스 코드>

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#include<queue>
using namespace std;
 
#define WALL 1
#define VIRUS 2
#define ACTIVE 0
#define INACTIVE -1
#define EMPTY -2
#define INIT 99999999
#define X first
#define Y second
 
const int dx[4= { 001-1 };
const int dy[4= { 1-100 };
 
int N, M;
int board[50][50];
int visited[50][50];
bool existVirus[50][50];
vector<pair<intint> > virus;
int virus_size;
pair<intint> selected[10];
bool isCheck[10];
int res = -1;
int emptyCnt;
int solve(int idx, int depth) {
    int ret = INIT;
    if (depth == M) {
        fill(&visited[0][0], &visited[49][50], EMPTY);
        fill(&existVirus[0][0], &existVirus[49][50], false);
        queue<pair<intint> > Q;
        for (int i = 0; i < M; i++) {
            auto e = selected[i];
            visited[e.X][e.Y] = ACTIVE;
            Q.push({ e.X, e.Y });
        }
        for (auto e : virus) {
            if (visited[e.X][e.Y] == EMPTY) visited[e.X][e.Y] = INACTIVE;
        }
        int cnt = 0;
        while (!Q.empty()) {
            auto cur = Q.front(); Q.pop();
            for (int dir = 0; dir < 4; dir++) {
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];
                if (nx < 0 || ny < 0 || nx >= N || ny >= N)continue;
                if (board[nx][ny] == WALL) continue;
            
                if (visited[nx][ny] == EMPTY) {
                    Q.push({ nx, ny });
                    visited[nx][ny] = visited[cur.X][cur.Y] + 1;
                }
                else if (visited[nx][ny] == INACTIVE) {
                    existVirus[nx][ny] = true;
                    Q.push({ nx, ny });
                    visited[nx][ny] = visited[cur.X][cur.Y] + 1;
                }
            }
        }
        
        int temp = -1;
        bool flag = false;
        for (int i = 0; i < N; i++) {
            if (flag) break;
            for (int j = 0; j < N; j++) {
                if (board[i][j] == WALL)continue;
                if (existVirus[i][j] == truecontinue;
                if (visited[i][j] == EMPTY) {
                    temp = INIT;
                    flag = true;
                    break;
                }
                temp = max(temp, visited[i][j]);
            }
        }
        ret = min(ret, temp);
    }
    else {
        for (int i = idx; i < virus_size; i++) {
            if (isCheck[i])continue;
            selected[depth] = virus[i];
            isCheck[i] = true;
            ret = min(ret, solve(i + 1, depth + 1));
            isCheck[i] = false;
        }
        
    }
    return ret;
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
            if (board[i][j] == VIRUS) virus.push_back({ i, j });
            else if (board[i][j] == 0)emptyCnt++;
        }
    }
    virus_size = virus.size();
    int ret = solve(00);
    if (ret == INIT) cout << -1;
    else cout << ret;
    return 0;
}
cs
반응형
반응형

문제 링크: https://www.acmicpc.net/problem/20055

 

20055번: 컨베이어 벨트 위의 로봇

길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부

www.acmicpc.net

<문제 풀이> 시뮬레이션, deque

컨베이어의 회전은 deque를 이용하면 쉽고, 효율적으로 회전하는 걸 구현할 수 있습니다.

-> deque에 각 칸을 순서대로 넣고 회전시킬 때 맨 뒤에 있는 원소를 맨 앞으로 보내면 됩니다.

이제 문제에서 나온 조건을 그대로 구현하면 되는데

1. 로봇은 1 ~ N번 칸에만 있을 수 있고, N번 칸에 도착한 로봇은 없애버리면 됩니다.

2. 1번 칸에 로봇이 없고 내구도가 0이 아니면 매 단계마다 추가할 수 있습니다.

 

<C++ 소스 코드>

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<iostream>
#include<deque>
#include<vector>
using namespace std;
 
class belt {
public:
    bool existRobot;
    int durability;
    belt(int existRobot, int durability) {
        this->existRobot = existRobot;
        this->durability = durability;
    }
};
 
deque<belt> dq;
int N, K;
int solve() {
    int ret = 0;
 
    int zeroCnt = 0;
    while (zeroCnt < K) { //4 내구도가 0인 칸의 개수가 k개 이상이라면 종료 
        //1
        ret++;
        dq.pop_front(); //buf 제거
        dq.push_front(dq.back()); //2N번을 1번으로
        dq.pop_back();
        dq.push_front({ false0 }); // buf 추가
        if (dq[N].existRobot) dq[N].existRobot = false//로봇이 내리는 위치에 존재하면 로봇을 내린다
        //2
        for(int i = N - 1; i >= 1; i--) {//가장 먼저 올라간 로봇부터
            if (!dq[i].existRobot) continue//로봇이 존재하면
            if (!dq[i + 1].existRobot && dq[i + 1].durability >= 1) {
                dq[i].existRobot = false;
                dq[i + 1].existRobot = true;
                dq[i + 1].durability--;
                if (dq[i + 1].durability == 0) zeroCnt++;
            }
        }
        if (dq[N].existRobot) dq[N].existRobot = false//로봇이 내리는 위치에 존재하면 로봇을 내린다
        //3
        if (dq[1].durability != 0 && !dq[1].existRobot) {
            dq[1].existRobot = true// 올리는 위치에 로봇을 올린다
            dq[1].durability--;
            if (dq[1].durability == 0) zeroCnt++;
        }
    }
 
    return ret;
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> N >> K;
    dq.push_front({false0});
    for (int i = 0; i < 2 * N; i++) {
        int d; cin >> d;
        dq.push_back({ false, d});
    }
    
    cout << solve();
    return 0;
}
cs

 

반응형

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 16236번] 아기 상어  (0) 2022.03.30
[백준 17142번] 연구소 3  (0) 2022.03.30
[백준 15685번] 드래곤 커브  (0) 2022.03.25
[백준 14890번] 경사로  (0) 2022.03.16
[백준 3055번] 탈출  (0) 2022.03.13
반응형

문제 링크: https://www.acmicpc.net/problem/15685

 

15685번: 드래곤 커브

첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커

www.acmicpc.net

<문제 풀이> 시뮬레이션

다음 세대의 드래건 커브를 구하는 방법은 이전 세대의 드래곤 커브가 지나온 방향을 역순으로 시계 방향으로 90도 회전해서 끝점부터 다시 가면 됩니다. 
시계 방향으로 90도 회전하는 방법은 아래와 같습니다.

if(방향 값 d == 3) d = 0

else d++

<C++ 소스 코드>

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<vector>
using namespace std;
 
int N;
 
int board[101][101];
vector<int> trace;
 
const int dx[4= {10-10};
const int dy[4= {0-101};
 
void getCurve(int x, int y, int d, int g) {
    trace.push_back(d);
    board[y + dy[d]][x + dx[d]] = 1
    y = y + dy[d];
    x = x + dx[d];
    while (g > 0) {
        int trace_size = trace.size();
        for (int i = trace_size - 1; i >= 0; i--) {
            if (trace[i] == 0) d = 1;
            else if (trace[i] == 1) d = 2;
            else if (trace[i] == 2) d = 3;
            else if (trace[i] == 3) d = 0;
            board[y + dy[d]][x + dx[d]] = 1;
            trace.push_back(d);
            y = y + dy[d]; 
            x = x + dx[d];
        }
        
        g--;
    }
    trace.clear();
};
 
int solve() {
    int ret = 0;
    for (int y = 0; y < 100; y++) {
        for (int x = 0; x < 100; x++) {
            if (board[y][x] == 1 && board[y + 1][x] == 1 && board[y][x + 1== 1 && board[y + 1][x + 1]) ret++;
        }
    }
    return ret;
}
 
int main(void) {
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        int x, y, d, g;
        cin >> x >>>> d >> g;
        board[y][x] = 1;
        getCurve(x, y, d, g);
    }
    cout << solve();
 
    return 0;
}
cs

 

반응형
반응형

문제 링크: https://www.acmicpc.net/problem/14890

 

14890번: 경사로

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

www.acmicpc.net

<문제 풀이> 구현
각 행의 0열부터 N-1까지 순회하면서 다음 두 가지를 경우를 체크해주면 됩니다.

1. 낮은 칸에서 높은칸으로 변화한 경우
    a. 높이 차가 1이 아닌 경우 경사로를 놓을 수 없으므로 지나갈 수 없다.
    b. 왼쪽 방향으로 길이가 L인 경사로를 놓는다.
        -> 높이가 변화한 지점에서부터 왼쪽으로 한 칸씩 이동해보면서 경사로를 놓아본다(높이가 같아야 함)
        -> 이때 방문 체크 배열을 사용해서 이전에 경사로를 놓았는지 여부도 함께 체크
        -> 경사로를 놓을 수 있는 위치이면 cnt을 1씩 증가
        -> 왼쪽으로 순회를 끝냈을 때 cnt와 L을 비교해서 같으면 경사로를 놓을 수 있고, 다르면 지나갈 수 없는 길
2. 높은 칸에서 낮은 칸으로 변화한 경우
        -> 1번이랑 같은 알고리즘


위의 알고리즘으로 함수를 구현해서 0 to N-1 행을 인자로 전달하면 됩니다.

 for (int i = 0; i < N; i++) {
        if (passalbe(i)) res++;
    }


이제 열에 대해서도 위와 똑같은 함수를 구현해도 되지만,
아래 처럼 배열을 90도로 회전시키는 함수를 구현해서, 배열을 회전하고 위 함수를 호출하면,
열에 대해서 알고리즘을 적용한 것과 동일합니다.


/*배열 90도 회전*/
void rotate() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            temp[i][j] = board[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            board[j][N - i - 1= temp[i][j];
        }
    }
}
/*열을 기준으로*/
rotate();
fill(&visited[0][0], &visited[99][100], 0);
for (int i = 0; i < N; i++) {
if (passalbe(i)) res++;
}




<C++ 소스 코드>

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
#include<iostream>
#include<algorithm>
using namespace std;
 
int N, L;
int board[100][100];
bool visited[100][100];
int temp[100][100];
/*배열 90도 회전*/
void rotate() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            temp[i][j] = board[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            board[j][N - i - 1= temp[i][j];
        }
    }
}
 
bool passalbe(int r) {
    int cur = board[r][0];
    for (int nc = 1; nc < N; nc++) {
        if (board[r][nc] > cur) { // 낮은 칸에서 높은 칸
            if (board[r][nc] - cur != 1return false// 높이 차가 1이 아니면
            int cnt = 0;
            cur = board[r][nc - 1];
            for (int j = nc - 1; j >= 0; j--) { //왼쪽으로 경사로를 놓아본다
                if (board[r][j] == cur && !visited[r][j]) {//높이는 모두 같아야하고 경사로를 중복해서 놓지 못한다
                    visited[r][j] = true;
                    cnt++;
                }
                else break;
                if (cnt == L) break;
            }
            if (cnt != L) return false//경사로를 놓을 수 없으면
        }
        else if (board[r][nc] < cur) { // 높은 칸에서 낮은곳
            if (cur - board[r][nc] != 1return false// 높이 차가 1이 아니면
            int cnt = 0;
            cur = board[r][nc];
            for (int j = nc; j < N; j++) { //오른쪽으로 경사로를 놓아본다
                if (board[r][j] == cur && !visited[r][j]) { //높이는 모두 같아야하고 경사로를 중복해서 놓지 못한다
                    visited[r][j] = true;
                    cnt++;
                }
                else break;
                if (cnt == L) break;
            }
            if (cnt != L) return false//경사로를 놓을 수 없으면
        }
        
        cur = board[r][nc];
    }
    return true;
}
 
int main(void) {
    cin >> N >> L;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }
    int res = 0;
    for (int i = 0; i < N; i++) {
        if (passalbe(i)) res++;
    }
    rotate();
    fill(&visited[0][0], &visited[99][100], 0);
    for (int i = 0; i < N; i++) {
        if (passalbe(i)) res++;
    }
    cout << res;
    return 0;
}
cs
반응형

+ Recent posts