Jenkins, NAVER Cloud Platform, Docker로 CI/CD 무중단 배포 환경 구축하기 - 1편Sticky||DevOpsCI/CD|NAVER CLOUD-Jenkins-CI/CD

이번 내용은 필자가 프로젝트를 진행하면서 처음으로 DevOps를 맡으면서 꼭 공유 하겠다고 마음 먹고 작성하였다.

CI/CD란?

  • CI(Continuous Integration)
    지속적인 통합을 의미한다. 이는 개발자를 위한 자동화 프로세스 중 하나이며 어플리케이션을 변경할 때 자동으로 빌드 및 테스트되어 Github 공유 레포지토리에 병합된다. 그렇기에 협업 시 발생할 수 있는 충돌문제를 해결할 수 있다.

  • CD(Continuous Deployment)
    지속적인 배포를 의미한다. 어플리케이션 변경 사항이 반영된 공유 레포지토리에서 사용자가 사용 가능한 환경까지 자동으로 배포하는 것을 말한다. 이를 통해 어플리케이션을 원활히 그리고 더 빠르게 제공하므로써 사용자의 피드백을 빠르게 반영할 수 있다.

아래는 필자가 맡은 프로젝트의 전체 시스템 구조이면서 동시에, CI/CD 과정을 볼 수 있다.

전체 시스템 구조

대부분 Travis CI, AWS, Docker, NGINX를 사용하여 CI/CD 무중단 배포를 구축한다는 점에서 비교하여 보아도 좋을 것이다.

선택의 순간들

AWS가 아닌 NAVER CLOUD 선택

AWS와 NAVER Cloud Platform을 사용해 보면서 느낀 것은 확실히 AWS의 기능이 훨씬 많고 유용하다.
그럼에도 NAVER Cloud Platform을 사용한 것은 40만 크레딧(지원 받았다.)이 제일 컸다.
AWS에는 무중단 배포까지 지원하는 서비스인 Blue-Green Deployment가 있는데 반해 NAVER Cloud는 없다…
그럼 굳이 왜 AWS를 선택하지 않았냐고 할 수 있는데 내가 직접 설정해서 구축하고 싶었기 때문이다. (사서 고생한다는 얘기)

Travis가 아닌 Jenkins 선택

Travis reference만 보아도 AWS랑 얼마나 죽이 잘 맞는지를 알 수 있다. (AWS말고도 Google Cloud, Azure도 지원한다.) 이미 NAVER Cloud를 선택한 이상 Travis는 더 어려운 방법으로 가는 길이라 생각했다. 오히려 설정할 수 있는 범위가 넓은 Jenkins를 택하는 것이 쉽다고 판단하였다. 처음에 AWS와 Travis로 자동화 배포 환경 구축을 연습했었는데, 개인적인 입장으로는 Jenkins가 좀 더 쉬운 것 같다.

40만 크레딧의 위엄으로 Jenkins를 도커가 아닌 Naver Cloud로 서버를 따로 구축했다. 지금 생각해보면 자원 낭비인 셈이지만 안정성 측면에서는 따로 서버를 두는 것이 좋다.

환경 구축하기

NAVER Cloud 사용 설명서는 무척 잘 되어 있고 AWS의 EC2나 S3와 같은 개념과 똑같기에 같은 방식으로 설정하면 된다.

  • NAVER Cloud의 Server = AWS의 EC2
  • NAVER Cloud의 Object Storage = AWS의 S3

아래와 같이 SourcePipeline 서비스를 이용하면 Github에서 push한 것을 자동으로 빌드하고 배포할 수 있는데, 아래 사진 우측 상단에 보이는 파이프라인 실행하기를 매번 클릭해줘야 한다…내가 원한건 push만 해도 자동화 빌드 및 배포이다. 결국 이걸 접고 Jenkins와 NAVER Cloud의 Server만 사용하기로 결정했다.

1. Jenkins 설정하기

Docker로 Jenkins 서버를 운영해도 되지만 NAVER Cloud에서 다음과 같이 지원하기에 사용하였다.
다만 수동으로 최신 업데이트 하는 것을 권장한다.

1-1. Jenkins 보안 설정

Jenkins는 기본적으로 보안 설정이 되어있지 않다.
Jenkins 관리 > Configure Global Security에서 설정할 수 있다.

  • 처음에 사용자의 가입을 허용하여 admin 계정을 생성한다. 팀원과 함께 작업한다면 팀원 각각 계정 생성하도록 둔다.
  • 계정 생성을 끝냈으면 ‘Matrix-based security’를 적절히 설정한다. (없다면 Matrix Authorization Strategy Plugin를 설치하자.)
    필자는 익명에게 읽기 권한 중 Job(Jenkins 작업 단위) 부분만 볼 수 있게 하였다. 이는 나중에 설정할 Github의 build status를 보여주기 위함이다.
    그리고 혼자 환경 구축을 담당 하였기에 팀원 계정 역시 익명과 같은 권한을 주었다.

1-2. 플러그인 설치하기

Jenkins 관리 > 플러그인 관리

  • Github plugin: Jenkins와 Github 통합
  • Global Slack Notifier Plugin: Slack 연동(Job 알림 설정)
  • Publish Over SSH: ssh로 빌드 파일 보내기
  • Embeddable Build Status Plugin: Github 레포지토리에 빌드 상태바 생성
  • Managed Scripts: Node.js 기반의 서버를 배포하기 위한 스크립트

1-3. Jenkins Global 설정하기

Jenkins 관리 > 시스템 설정 > GitHub Servers에서 다음과 같이 설정한다.

Credentials 설정을 위해 자신의 Github > Settings > Developer settings > Personal access tokens에서 다음과 같이 토큰을 생성한다.

생성 후 화면에 보이는 secret 문자열을 아래의 Secret에 입력한다.

1-4. 프로젝트 생성 및 설정하기

새로운 Item을 클릭하고 프로젝트 이름을 입력, Freestyle을 누른다.

  • 다음과 같이 프로젝트 url을 입력하고 Credentials를 설정한다.

이 작업은 Github을 연동하는 것인데, ID와 PW로 연동하면 보안에 취약하기에 ssh키로 연동하였다.

ssh 키 생성하기

  • ssh로 Jenkins 서버에 원격 접속하여 다음을 입력한다.
    1
    ssh-keygen -t rsa -f id_rsa

id_rsa, id_rsa.pub 를 포함해 총 4개의 키가 생성된다.

  • 아래 Add 표시를 눌러 cat ~/.ssh/id_rsa 입력 후 나오는 private key를 넣어준다

BEGIN ~부터 모두 복사하여 입력한다.

  • Github에 공개 키 등록하기.

cat ~/.ssh/id_rsa.pub 를 입력하면 나오는 공개 키를 프로젝트 레포지토리의 Setting > Deploy keys에 등록한다.

이제 Jenkins과 Github을 연동시켰기에, Jenkins에 코드를 가져올 수 있게 되었다.

  • 다음으로는 push했을 때 Jenkins가 push 이벤트를 받을 수 있도록 설정 해보자.
    마찬가지로 레포지토리의 setting > webhooks 에서 빨간색 네모박스에 Jenkins ip 주소를 입력하고 나머지는 그대로 입력한다.

  • Github에서의 설정은 끝났고 Jenkins 프로젝트에서 다음을 체크함으로써 이벤트 설정은 끝이 났다.
    이젠 push만 하면 Jenkins 해당 프로젝트에서 빌드가 시작됨을 볼 수 있다.

빌드 기록을 통해 소스 코드가 빌드 중인지 빌드 완료 되었는지를 확인할 수 있다.

이것으로 Jenkins로 CI 환경 구축은 끝이 났다. 2편에서는 CD 환경 구축과 무중단 배포를 구축해보겠다.

2편 보러가기

백준 17472번 다리 만들기 2|AlgorithmBOJ|Algorithm

#17472. 다리 만들기 2

Problem

Solution

  1. 각 섬에 고유 번호 붙이기(오름차순)
    섬끼리 연결을 해야하기 때문에 이를 식별해주어야 한다.
    BFS or DFS를 이용하여 구할 수 있고 필자는 BFS를 사용하였다.
  2. 각 섬들마다 연결시키는 모든 경우를 구하되, 각 경우마다 연결이 가능한지 거리를 측정하면서 확인한다.
    → 연결이 가능하면 해당 다리를 저장한다.(어디에서 어디로 연결되고 그럴 때 최소 비용 저장)
  3. 다리를 선택해서 1개 이상 선택했을 때부터 모든 섬을 연결 시킬 수 있는지 확인한다.
    → 모든 섬을 연결할 수 있으면 최소비용 갱신

Answer

  • 완탐 코드 보기

    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
    148
    149
    150
    151
    152
    153
    154
    155
    156
    #include <iostream>
    #include <cstring>
    #include <queue>
    #include <vector>
    using namespace std;
    int N, M, total_island, ans = 1e9;
    int map[10][10];
    bool visited[10][10]; // 섬에 번호 붙일 때 방문 체크 용도
    int dist[7][7]; // dist[a][b]: a에서 b로 가는 경로 비용, 기본값 1000
    int dx[4] = { -1, 1, 0, 0 };
    int dy[4] = { 0, 0, -1, 1 };
    vector<pair<int, int>> Island_pos[11]; // Island_pos[i]: i번 섬의 모든 좌표
    vector<pair<pair<int, int>, int>> bridge_list; // a, b, c : a->b의 비용이 c인 다리 목록
    bool connect[7][7]; // a, b와의 연결 상태 확인 용도
    bool connect_island[7]; // i번 섬의 방문 체크 용도
    bool selected[7 * 7]; // 간선의 모든 경우를 담기 위함( N(N-1)/2 )
    void BFS(int x, int y, int id) { // 섬에 번호 붙이기
    	queue<pair<int, int> > q;
    	q.push({ x, y });
    	visited[x][y] = true;
    	map[x][y] = id;
    	Island_pos[id].push_back({ x, y });
    	while (!q.empty()) {
    		int x = q.front().first;
    		int y = q.front().second;
    		q.pop();
    		for (int dir = 0; dir < 4; ++dir) {
    			int d_x = x + dx[dir];
    			int d_y = y + dy[dir];
    			if (d_x > -1 && d_y > -1 && d_x < N && d_y < M) {
    				if (visited[d_x][d_y] || map[d_x][d_y] != 1) continue;
    				visited[d_x][d_y] = true;
    				map[d_x][d_y] = id;
    				Island_pos[id].push_back({ d_x, d_y });
    				q.push({ d_x, d_y });
    			}
    		}
    	}
    }
    void Go(int x, int y, int dir, int len, int start, int end) { // 거리 측정하기
    	int nx = x + dx[dir];
    	int ny = y + dy[dir];
    	if (nx < 0 || ny < 0 || nx >= N || ny >= M) return;
    	if (map[nx][ny] == end) {
    		if (len > 1) { // 거리 2이상인 경우만 연결 가능
    			if (dist[start][end] > len) { // 최소 거리 갱신
    				dist[start][end] = len;
    				dist[end][start] = len;
    			}
    		}
    		return;
    	}
    	else if (map[nx][ny] == 0) Go(nx, ny, dir, len + 1, start, end);
    	else return;
    }
    void MakeBridge(int start, int end) {
    	//Start에 해당되는 섬의 모든 좌표를 end에 해당되는 섬까지 도달해본다.
    	for (int i = 0; i < Island_pos[start].size(); i++)
    	{
    		int x = Island_pos[start][i].first;
    		int y = Island_pos[start][i].second;

    		for (int dir = 0; dir < 4; ++dir) {
    			int nx = x + dx[dir];
    			int ny = y + dy[dir];
    			if (nx > -1 && ny > -1 && nx < N && ny < M) {
    				if (map[nx][ny] == 0) Go(nx, ny, dir, 1, start, end); // 한 방향으로 가야함, 0인 지점 방문이니 거리 1
    			}
    		}
    	}
    }
    void GetDistance() { // 섬들끼리 1:1로 연결시키는 모든 경우
    	for (int i = 1; i < total_island; i++)
    	{
    		for (int j = i + 1; j < total_island; j++)
    		{
    			MakeBridge(i, j);
    			if (dist[i][j] == 1000) continue; // 연결 불가능한 경우
    			bridge_list.push_back({ {i, j}, dist[i][j] }); // (i -> j : 비용) 저장
    		}
    	}
    }
    bool CheckConnect() { // 조건에 맞게 모든 섬이 연결되어있는지 확인
    	memset(connect, false, sizeof(connect));
    	memset(connect_island, false, sizeof(connect_island));
    	for (int i = 0; i < bridge_list.size(); i++) // 선택한 다리 연결 표시
    	{
    		if (selected[i]) { // 연결 표시 (x->y, y->x)
    			int x = bridge_list[i].first.first;
    			int y = bridge_list[i].first.second;
    			connect[x][y] = connect[y][x] = true;
    		}
    	}
    	queue<int> q; 
    	q.push(1); // 1번 섬(섬은 최소 2개)
    	connect_island[1] = true; // 1번 섬 방문 체크 

    	int Island_cnt = 1;
    	bool flag = false;
    	while (!q.empty()) { // 모든 섬 방문가능한지 체크하는 부분
    		int cur = q.front();
    		q.pop();
    		if (Island_cnt == total_island - 1) {
    			flag = true;
    			break;
    		}
    		for (int i = 1; i < total_island; i++)
    		{
    			if (cur == i) continue;
    			if (connect[cur][i] && connect_island[i] == false) { // 현재 섬과 i번 섬이 연결되어있고 i번 섬을 방문하지 않았을 때
    				connect_island[i] = true;
    				q.push(i);
    				Island_cnt++;
    			}
    		}
    	}
    	return flag;
    }
    void SelectBridge(int idx, int cnt, int sum) { 
    	if (cnt >= 1) {
    		if (CheckConnect() == true) {
    			if (ans > sum) ans = sum;
    		}
    	}
    	for (int i = idx; i < bridge_list.size(); ++i) {
    		if (selected[i] == true) continue;
    		selected[i] = true;
    		SelectBridge(i, cnt + 1, sum + bridge_list[i].second);
    		selected[i] = false;
    	}
    }
    int main() {
    	for (int i = 0; i < 7; ++i) {
    		for (int j = 0; j < 7; j++) {
    			dist[i][j] = 1000;
    		}
    	}
    	cin >> N >> M;
    	for (int i = 0; i < N; ++i) {
    		for (int j = 0; j < M; ++j) {
    			cin >> map[i][j];
    		}
    	}
    	int id = 1;
    	for (int i = 0; i < N; ++i) {
    		for (int j = 0; j < M; ++j) {
    			if (map[i][j] != 0 && !visited[i][j]) BFS(i, j, id++);
    		}
    	}
    	total_island = id;
    	GetDistance();
    	SelectBridge(0, 0, 0);
    	if (ans == 1e9) ans = -1;
    	cout << ans << "\n";
    	return 0;
    }

    Solution

  • 위 방식에서 1, 2까지는 동일

  • 크루스칼 알고리즘을 사용한다.

Answer

  • 코드 보기
    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
    148
    #include <iostream>
    #include <vector>
    #include <queue>
    #include <algorithm>
    using namespace std;
    typedef pair<int, int> d;
    struct Bridge {
    	int from;
    	int to;
    	int len;
    };
    int N, M, total, ans = 10000;
    int map[10][10];
    bool visited[10][10];
    int parent[7];
    int dx[4] = { -1, 1, 0, 0 };
    int dy[4] = { 0, 0, -1, 1 };
    vector<d> island[7];
    vector<Bridge> bridge;

    int Go(int from, int to) {
    	int len = 10000;
    	for (int i = 0; i < island[from].size(); i++){
    		int x = island[from][i].first;
    		int y = island[from][i].second;
    		for (int dir = 0; dir < 4; ++dir) {
    			int nx = x; int ny = y;
    			int cur = 0;
    			while (true) {
    				if (len <= cur) break;
    				nx += dx[dir];
    				ny += dy[dir];
    				if (nx < 0 || ny < 0 || nx >= N || ny >= M) break;
    				if (map[nx][ny] == 0) {
    					cur++;
    				}
    				else if (map[nx][ny] == to) {
    					if (cur < 2) break;
    					if (len > cur) len = cur;
    					break;
    				}
    				else break;
    			}
    		}
    	}
    	return len;
    }
    void GetDistance() {
    	Bridge b;
    	for (int i = 1; i <= total; ++i) {
    		for (int j = i + 1; j <= total; ++j) {
    			b.from = i; b.to = j;
    			b.len = Go(i, j);
    			if (b.len == 10000) continue;
    			bridge.push_back(b);
    		}
    	}
    }
    void BFS(int r, int c, int id) {
    	queue<d> q;
    	q.push({ r, c });
    	visited[r][c] = true;
    	map[r][c] = id;
    	island[id].push_back({ r, c });
    	while (!q.empty()) {
    		int x = q.front().first;
    		int y = q.front().second;
    		q.pop();
    		for (int dir = 0; dir < 4; ++dir) {
    			int nx = x + dx[dir];
    			int ny = y + dy[dir];
    			if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
    			if (map[nx][ny] != 1 || visited[nx][ny]) continue;
    			visited[nx][ny] = true;
    			map[nx][ny] = id;
    			island[id].push_back({ nx, ny });
    			q.push({ nx, ny });
    		}
    	}
    }
    void MakeLabel() {
    	int id = 1;
    	for (int i = 0; i < N; ++i) {
    		for (int j = 0; j < M; ++j) {
    			if (map[i][j] == 0 || visited[i][j]) continue;
    			BFS(i, j, id++);
    		}
    	}
    	total = id - 1;
    	for (int i = 1; i <= total; ++i) {
    		parent[i] = i;
    	}
    }
    int cmp(Bridge a, Bridge b) {
    	return a.len < b.len;
    }
    int FindParent(int idx) {
    	if (parent[idx] == idx) return idx;
    	else return FindParent(parent[idx]);
    }
    void Union(int from, int to) {
    	int p1 = FindParent(parent[from]);
    	int p2 = FindParent(parent[to]);
    	if (p1 < p2) {
    		parent[to] = p1;
    		parent[p2] = p1;
    	}
    	else {
    		parent[from] = p2;
    		parent[p1] = p2;
    	}
    }
    bool CheckConnection() {
    	for (int i = 1; i <= total; ++i) {
    		if (FindParent(parent[i]) != 1) return false;
    	}
    	return true;
    }
    void Kruskal() {
    	sort(bridge.begin(), bridge.end(), cmp);
    	int cost = 0;
    	for (int i = 0; i < bridge.size(); ++i) {
    		int from = bridge[i].from; int to = bridge[i].to;
    		if(FindParent(from) == FindParent(to)) continue;
    		else {
    			Union(from, to);
    			cost += bridge[i].len;
    		}
    	}
    	if (CheckConnection()) ans = cost;
    }
    void Solve() {
    	MakeLabel();
    	GetDistance();
    	Kruskal();
    }
    int main() {
    	cin >> N >> M;
    	for (int i = 0; i < N; i++) {
    		for (int j = 0; j < M; j++) {
    			cin >> map[i][j];
    		}
    	}
    	Solve();
    	if (ans == 10000) ans = -1;
    	cout << ans << "\n";
    	return 0;
    }
백준 17471번 게리맨더링|AlgorithmBOJ|Algorithm

#17471. 게리맨더링

Problem

Solution

  • city[n][j] = n번째 구역과 인접한구역 j는 1로 표시, 아니면 0으로 표시
  1. 한 지역의 구역을 정한다. (중복x, 오름차순으로) - (1,2,3) 과 (2,1,3)은 같은 조합이기에

  2. 정한 구역이 이어져 있는지 DFS를 통해 확인한다.

    1. 방문표시

    2. 전체 구역 탐색하여 해당 지역에 속하고 인접할 때, 해당 구역 탐색

      DFS 시작 지점은 해당 지역에서 한 구역으로 지정한다. (그래야 모두 인접해있는지 확인 가능)

      2개의 지역 모두 DFS 탐색 후에 check 표시가 모두 되어있지 않으면 return한다.

      규칙에 맞게 구역이 나누어져 있지 않다는 뜻이기 때문이다.

1 Try

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
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int N, ans = 1e9;
bool selected[11];
int people[11];
int city[11][11];
bool check[11];
void getDifference() {
	int a_sum = 0, b_sum = 0;
	for (int i = 1; i <= N; ++i) {
		if (selected[i]) a_sum += people[i];
		else b_sum += people[i];
	}
	int res = abs(a_sum - b_sum);
	if (res < ans) ans = res;
}
void DFS(int n, int status) {
	check[n] = true;
	for (int i = 1; i <= N; ++i) {
		if (check[i]) continue;
		if (status == 1) {
			if (selected[i] && city[n][i]) {
				check[i] = true;
				DFS(i, status);
			}
		}
		else {
			if (!selected[i] && city[n][i]) {
				check[i] = true;
				DFS(i, status);
			}
		}
	}
}
void Solve() {
	memset(check, 0, sizeof(check));
	for (int i = 1; i <= N; ++i) {
		if (selected[i]) {
			DFS(i, 1); break;
		}
	}
	for (int i = 1; i <= N; ++i) {
		if (!selected[i]) {
			DFS(i, 0); break;
		}
	}
	for (int i = 1; i <= N; ++i) {
		if (!check[i]) return;
	}
	getDifference();
}
void SelectArea(int n, int cnt) {
	if (cnt >= N) return;
	if (cnt >= 1) {
		Solve();
	}
	for (int i = n; i <= N; ++i) {
		if (selected[i]) continue;
		selected[i] = true;
		SelectArea(i, cnt + 1);
		selected[i] = false;
	}
}
int main() {
	cin >> N;
	for (int i = 1; i <= N; ++i) {
		cin >> people[i];
	}
	for (int i = 1; i <= N; ++i) {
		int cnt; cin >> cnt;
		for (int j = 0; j < cnt; ++j) {
			int n; cin >> n;
			city[i][n] = 1;
		}
	}
	SelectArea(1, 0);
	if (ans == 1e9) ans = -1;
	cout << ans << "\n";
	return 0;
}
백준 17406번 배열 돌리기 4|AlgorithmBOJ|Algorithm

#17406. 배열 돌리기 4

Problem

Solution

  • 회전 연산 순서를 정한다. (0, 1, 2) 와 (1, 0, 2)는 다른 순서이다!
  • 가장 바깥쪽 부터 시계방향으로 각 원소들을 회전시킨다.
    가장 바깥쪽 크기는 2*s+1이다.
  • 시작 지점부터 시작해서 +1씩, 크기는 -2씩 변경하며 회전시킨다.
  • 중앙 지점으 만나면 더이상 회전시킬 수 없으므로 종료한다.
  • 회전은 아래와 같은 방법으로 진행한다.
  • “미세먼지 안녕!” 문제에서 설명한 배열 회전 방법과 동일하다.
    여기선 시계방향이므로 2번째 그림이 이에 해당한다.

1 Try

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
#include <iostream>
using namespace std;
int N, M, K, ans = 1e9;
int arr[50][50];
int copy_arr[50][50];
int order[6];
bool selected[6];
struct Inst {
	int r, c, s;
}ins[6];
void CopyArray() {
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			copy_arr[i][j] = arr[i][j];
		}
	}
}
int getSum() {
	int res = 1e9;
	for (int i = 0; i < N; ++i) {
		int sum = 0;
		for (int j = 0; j < M; ++j) {
			sum += copy_arr[i][j];
		}
		if (res > sum) res = sum;
	}
	return res;
}
void Rotate() {
	CopyArray();
	for (int i = 0; i < K; ++i) {
		int len = ins[order[i]].s * 2 + 1; // 가장 바깥쪽 크기
		int mid_r = ins[order[i]].r; // 중심 좌표
		int mid_c = ins[order[i]].c;
		int start_r = ins[order[i]].r - ins[order[i]].s; // 시작 좌표
		int start_c = ins[order[i]].c - ins[order[i]].s;
		while (true) {
			if (mid_r == start_r && mid_c == start_c) break; // 중심점이면 종료
			int temp = copy_arr[start_r][start_c]; // 시작지점 값만 빼놓기
			int end_r = start_r + len - 1; // 끝 행
			int end_c = start_c + len - 1; // 끝 열
			for (int r = start_r; r < start_r + len - 1; ++r) { // (1)
				copy_arr[r][start_c] = copy_arr[r + 1][start_c];
			}
			for (int c = start_c; c < start_c + len - 1; ++c) { // (2)
				copy_arr[end_r][c] = copy_arr[end_r][c + 1];
			}
			for (int r = end_r; r > start_r; --r) { // (3)
				copy_arr[r][end_c] = copy_arr[r - 1][end_c];
			}
			for (int c = end_c; c > start_c + 1; --c) { // (4)
				copy_arr[start_r][c] = copy_arr[start_r][c - 1];
			}
			copy_arr[start_r][start_c + 1] = temp; // 빼놓은 값 넣기
			start_r++; start_c++; len -= 2; // 시작지점 및 길이 갱신
		}
	}
	int res = getSum();
	if (ans > res) ans = res;
}
void SelectOrder(int cnt) {
	if (cnt == K) {
		Rotate();
		return;
	}
	for (int i = 0; i < K; ++i) {
		if (selected[i]) continue;
		order[cnt] = i;
		selected[i] = true;
		SelectOrder(cnt + 1);
		selected[i] = false;
	}
}
int main() {
	cin >> N >> M >> K;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			cin >> arr[i][j];
		}
	}
	for (int i = 0; i < K; ++i) {
		int r, c, s;
		cin >> r >> c >> s;
		ins[i] = { r-1, c-1, s };
	}
	SelectOrder(0);
	cout << ans << "\n";
	return 0;
}
백준 17298번 오큰수|AlgorithmBOJ|Algorithm

#17298. 오큰수

문제링크

Problem

  • 길이가 N인 수열

Goal: 각 원소에 대해 자신보다 오른쪽에 있으면서 크고 가장 왼쪽에 위치한 수를 구하여라
없다면 -1 출력

Solution

  • Stack을 사용한다.
  • 단계는 문제에 예시로 있는 입력 값으로 설명을 하겠다.

Untitled

오른쪽 순서로 단계가 진행된다.

  1. 원소의 최댓값은 최대 1000000(백만)이기에 +1값을 MAX로 주었다.
  2. 수열의 맨 오른쪽부터 진행한다.
  • 사이클
    1. 비교 대상인 입력값과 스텍에 있는 값을 비교하여 스텍에 있는 값이 클 때까지 작업(비교)을 수행한다.
    2. 만약 MAX가 스텍의 top이라면 이미 자신보다 큰 수가 없다는 뜻이기에 -1를 출력값에 넣어준다.
    3. 그게 아니라면 스텍의 top은 항상 현재 입력값보다 크면서 가장 오른쪽에 있는 수이다. 그렇기에 top을 출력값에 넣어준다.

1 Try

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
#include <cstdio>
#include <stack>
#include <vector>
#define MAX 1000001
using namespace std;
stack<int> a, ans, num;
int main() {
	int n, input;
	scanf("%d", &n);
	for(int i = 0; i < n; ++i) {
		scanf("%d", &input);
		num.push(input);
	}
	a.push(MAX);
	while(!num.empty()) {
		while(a.top() <= num.top()) a.pop(); // 같을 때도 pop을 해주어야 다음 큰 값을 비교가능
		if(a.top() == MAX) ans.push(-1);
		else ans.push(a.top());
		a.push(num.top()); num.pop();
	}
	while(!ans.empty()) {
		printf("%d ", ans.top());
		ans.pop();
	}
	printf("\n");
	return 0;
}
백준 17281번 ⚾(야구공)|AlgorithmBOJ|Algorithm

#17281. ⚾

Problem

Solution

시뮬레이션 문제이다. 문제의 설명에 맞게 잘 구현하면 큰 어려움은 없는 문제

  1. 타자의 순번을 정한다. (1번 선수는 4번 타자로 고정) → (1, 2, 3)과 (2, 1, 3)은 다른 순서임
  2. 1이닝부터 N이닝까지 경기를 진행한다.
  3. 각 이닝별 진행 흐름
    1. 이전 순번 바로 다음부터 순번이 진행된다. (첫 이닝은 1번부터(인덱스상 0))
    2. 아웃이 3번이 될 때까지 진행한다.
    3. 1루, 2루, 3루에 선수가 있는지 표시하는 is_there 변수를 사용하여 진행한다.

1 Try

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, ans;
int info[50][9]; // 각 이닝별 타자 정보
int order[9]; // 타자 순번
bool selected[9];
void Game() {
	int idx = 0, score = 0; // 순번 인덱스, 현재 점수
	for(int inning = 0; inning < N; ++inning) {
		bool is_there[3] = { false, false, false }; // 1, 2, 3루
		int out = 0;
		while (true) {
			if (info[inning][order[idx]] == 0) { // 아웃
				out++;
			}
			else if (info[inning][order[idx]] == 1) { // 1루타
				if (is_there[2]) { // 3루타 -> 홈
					score++; is_there[2] = false;
				}
				for (int i = 1; i != -1; --i) { // 각각 1 전진
					if (is_there[i]) {
						is_there[i + 1] = true;
						is_there[i] = false;
					}
				}
				is_there[0] = true; // 1루 전진
			}
			else if (info[inning][order[idx]] == 2) { // 2루타
				for (int i = 1; i < 3; ++i) { // 2루, 3루 -> 홈
					if (is_there[i]) {
						score++; is_there[i] = false;
					}
				}
				if (is_there[0]) { // 1루 -> 3루
					is_there[2] = true; is_there[0] = false;
				}
				is_there[1] = true; // 2루 전진
			}
			else if (info[inning][order[idx]] == 3) { // 3루타
				for (int i = 0; i < 3; ++i) { // 1, 2, 3루 -> 홈
					if (is_there[i]) {
						score++; is_there[i] = false;
					}
				}
				is_there[2] = true; // 3루 전진
			}
			else { // 홈런
				for (int i = 0; i < 3; ++i) {
					if (is_there[i]) {
						score++; is_there[i] = false;
					}
				}
				score++;
			}
			idx = (idx + 1) % 9; // 다음 순번
			if (out == 3) break; // 3진 아웃
		}
	}
	if (ans < score) ans = score;
}
void SelectOrder(int cnt) {
	if (cnt == 9) {
		Game();
		return;
	}
	if (cnt == 3) cnt++;
	for (int i = 1; i < 9; ++i) {
		if (selected[i]) continue; 
		selected[i] = true;
		order[cnt] = i;
		SelectOrder(cnt + 1);
		selected[i] = false;
	}
}
int main() {
	cin >> N;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < 9; ++j) {
			cin >> info[i][j];
		}
	}
	selected[0] = true; order[3] = 0; // 1번 선수 4번째 고정
	SelectOrder(0);
	cout << ans << "\n";
	return 0;
}
백준 17144번 미세먼지 안녕!|AlgorithmBOJ|Algorithm

#17144. 미세먼지 안녕!

문제링크

Problem

  • 공기청정기 항상 왼쪽 열 (두 행 차지)
  • 그외 미세먼지나 빈 칸이 존재
  • 1초 동안 일어나는 일
  1. 미세먼지 확산
    4방향(상하좌우)
    공기청정기나 경계를 벗어나는 칸은 확산이 일어나지 않음
    미세먼지 양/5 만큼 확산된다. (각 방향에 대해 한 칸)
    확산된 후 남은 미세먼지 양은
    현재 미세먼지 양 - 현재 미세먼지 양/5 * 확산된 방향 개수
  2. 공기청정기 작동 (바람)
    위쪽 → 반시계방향 순환
    아래쪽 → 시계방향 순환
    미세먼지가 바람의 방향대로 한 칸씩 이동
    미세먼지가 공기청정기로 들어가면 모두 정화

Goal: T초가 지난 후 남아있는 미세먼지의 양

Solution

1초가 지날 때마다 다음과 같은 작업이 수행된다.

  1. 미세먼지 확산
  2. 바람으로 인한 이동
  • 미세먼지 확산

5 이상인 값만 확산이 일어난다.
확산이 일어나기 전에 queue에 이 값과 이 값이 있는 위치를 저장해놓는다.
(값을 저장해야 올바른 값을 구할 수 있음)
queue에서 하나씩 꺼내어 4가지 방향을 확인한다.
(공기청정기 있는 곳과 경계를 넘는 곳은 불가능)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void spread() {
	int len = q.size();
	for (int i = 0; i < len; ++i) {
		int r = q.front().r;
		int c = q.front().c;
		int mid = q.front().value;
		q.pop();
		for (int j = 0; j < 4; ++j) {
			int x = r + dx[j];
			int y = c + dy[j];
			if (isBound(x, y) && map[x][y] != -1) {
				map[x][y] += mid / 5;
				map[r][c] -= mid / 5;
			}
		}
	}
}

확산이 가능하다면 연산을 수행한다.

  • 바람으로 인한 이동

아래 순서대로 map을 바꿔준다.

공기청정기로 들어간다는 것은 굳이 값을 바꿔줄 필요 없이 전의 값이 이를 덮어주기만 하면 된다. (1번째) → 아래 2번 화살표가 잘못되었습니다….(반대입니다)
공기청정기에서 나아가는 바람으로(4번째) 값을 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
void wind() {
	int i, j, clean_row = clean[0];
// 위쪽
	for (i = clean_row - 2; i >= 0; --i) {
		map[i + 1][0] = map[i][0];
	}
	for (j = 1; j < total_col; ++j) {
		map[0][j - 1] = map[0][j];
	}
	for (i = 1; i <= clean_row; ++i) {
		map[i - 1][total_col - 1] = map[i][total_col - 1];
	}
	for (j = total_col - 1; j >= 1; --j) {
		map[clean_row][j + 1] = map[clean_row][j];
	}
// 아래쪽
	map[clean_row][1] = 0;
	clean_row = clean[1];
	for (i = clean_row + 2; i < total_row; ++i) {
		map[i - 1][0] = map[i][0];
	}
	for (j = 1; j < total_col; ++j) {
		map[total_row - 1][j - 1] = map[total_row - 1][j];
	}
	for (i = total_row - 2; i >= clean_row; --i) {
		map[i + 1][total_col - 1] = map[i][total_col - 1];
	}
	for (j = total_col - 2; j >= 1; --j) {
		map[clean_row][j + 1] = map[clean_row][j];
	}
	map[clean_row][1] = 0;
}

1 Try

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
#include <cstdio>
#include <queue>
#define MAX 50
using namespace std;
int total_row, total_col, time;
int map[MAX][MAX];
int clean[2]; 
struct info {
	int r, c, value;
};
queue<info> q;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
bool isBound(int r, int c) {
	if (r > -1 && c > -1 && r < total_row && c < total_col) return true;
	return false;
}
void spread() {
	int len = q.size();
	for (int i = 0; i < len; ++i) {
		int r = q.front().r;
		int c = q.front().c;
		int mid = q.front().value;
		q.pop();
		for (int j = 0; j < 4; ++j) {
			int x = r + dx[j];
			int y = c + dy[j];
			if (isBound(x, y) && map[x][y] != -1) {
				map[x][y] += mid / 5;
				map[r][c] -= mid / 5;
			}
		}
	}
}
void wind() {
	int i, j, clean_row = clean[0];
	for (i = clean_row - 2; i >= 0; --i) {
		map[i + 1][0] = map[i][0];
	}
	for (j = 1; j < total_col; ++j) {
		map[0][j - 1] = map[0][j];
	}
	for (i = 1; i <= clean_row; ++i) {
		map[i - 1][total_col - 1] = map[i][total_col - 1];
	}
	for (j = total_col - 1; j >= 1; --j) {
		map[clean_row][j + 1] = map[clean_row][j];
	}
	map[clean_row][1] = 0;
	clean_row = clean[1];
	for (i = clean_row + 2; i < total_row; ++i) {
		map[i - 1][0] = map[i][0];
	}
	for (j = 1; j < total_col; ++j) {
		map[total_row - 1][j - 1] = map[total_row - 1][j];
	}
	for (i = total_row - 2; i >= clean_row; --i) {
		map[i + 1][total_col - 1] = map[i][total_col - 1];
	}
	for (j = total_col - 2; j >= 1; --j) {
		map[clean_row][j + 1] = map[clean_row][j];
	}
	map[clean_row][1] = 0;
}
int main() {
	int answer, idx = 0;
	scanf("%d %d %d", &total_row, &total_col, &time);
	for (int i = 0; i < total_row; ++i) {
		for (int j = 0; j < total_col; ++j) {
			scanf("%d", &map[i][j]);
			if (map[i][j] >= 5) q.push({ i, j, map[i][j] });
		}
		if (map[i][0] == -1) clean[idx++] = i;
	}
	while (time--) {
		answer = 0;
		spread();
		wind();
		for (int i = 0; i < total_row; ++i) {
			for (int j = 0; j < total_col; ++j) {
				if (map[i][j] > 0) answer += map[i][j];
				if (map[i][j] >= 5) q.push({ i, j, map[i][j] });
			}
		}
	}
	printf("%d\n", answer);
	return 0;
}

테스트 케이스는 다 맞다는데 틀렸단다…ㅎ

그 이유는 MAX를 50이기 때문이다. (응? 뭔 🙄🤔…다음부터 넉넉히 잡자..)
MAX 51로 고쳐주니까 바로 정답 처리 되었다.

2 Try

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
#include <cstdio>
#include <queue>
#define MAX 51
using namespace std;
int total_row, total_col, time;
int map[MAX][MAX];
int clean[2];
struct info {
	int r, c, value;
};
queue<info> q;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
bool isBound(int r, int c) {
	if (r > -1 && c > -1 && r < total_row && c < total_col) return true;
	return false;
}
void spread() {
	while(!q.empty()) {
		int r = q.front().r;
		int c = q.front().c;
		int mid = q.front().value;
		q.pop();
		for (int j = 0; j < 4; ++j) {
			int x = r + dx[j];
			int y = c + dy[j];
			if (isBound(x, y) && map[x][y] != -1) {
				map[x][y] += mid / 5;
				map[r][c] -= mid / 5;
			}
		}
	}
}
void wind() {
	int i, j, clean_row = clean[0];
	for (i = clean_row - 2; i >= 0; --i) {
		map[i + 1][0] = map[i][0];
	}
	for (j = 1; j < total_col; ++j) {
		map[0][j - 1] = map[0][j];
	}
	for (i = 1; i <= clean_row; ++i) {
		map[i - 1][total_col - 1] = map[i][total_col - 1];
	}
	for (j = total_col - 1; j >= 1; --j) {
		map[clean_row][j + 1] = map[clean_row][j];
	}
	map[clean_row][1] = 0;
	clean_row = clean[1];
	for (i = clean_row + 2; i < total_row; ++i) {
		map[i - 1][0] = map[i][0];
	}
	for (j = 1; j < total_col; ++j) {
		map[total_row - 1][j - 1] = map[total_row - 1][j];
	}
	for (i = total_row - 2; i >= clean_row; --i) {
		map[i + 1][total_col - 1] = map[i][total_col - 1];
	}
	for (j = total_col - 2; j >= 1; --j) {
		map[clean_row][j + 1] = map[clean_row][j];
	}
	map[clean_row][1] = 0;
}
int main() {
	int answer, idx = 0;
	scanf("%d %d %d", &total_row, &total_col, &time);
	for (int i = 0; i < total_row; ++i) {
		for (int j = 0; j < total_col; ++j) {
			scanf("%d", &map[i][j]);
			if (map[i][j] >= 5) q.push({ i, j, map[i][j] });
		}
		if (map[i][0] == -1) clean[idx++] = i;
	}
	while (time--) {
		answer = 0;
		spread();
		wind();
		for (int i = 0; i < total_row; ++i) {
			for (int j = 0; j < total_col; ++j) {
				if (map[i][j] > 0) answer += map[i][j];
				if (map[i][j] >= 5) q.push({ i, j, map[i][j] });
			}
		}
	}
	printf("%d\n", answer);
	return 0;
}

Debug

  • 코드
    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
    #include <cstdio>
    #include <queue>
    #define MAX 50
    using namespace std;
    int total_row, total_col, time;
    int map[MAX][MAX];
    int clean[2]; // 공기청정기 위치(무조건 0열)
    struct info {
    	int r, c, value;
    };
    queue<info> q;
    // 상하좌우
    int dx[4] = { -1, 1, 0, 0 };
    int dy[4] = { 0, 0, -1, 1 };
    bool isBound(int r, int c) {
    	if (r > -1 && c > -1 && r < total_row && c < total_col) return true;
    	return false;
    }
    // 1. 미세먼지 확산
    void spread() {
    	int len = q.size();
    	for (int i = 0; i < len; ++i) {
    		int r = q.front().r;
    		int c = q.front().c;
    		int mid = q.front().value;
    		q.pop();
    		for (int j = 0; j < 4; ++j) {
    			int x = r + dx[j];
    			int y = c + dy[j];
    			if (isBound(x, y) && map[x][y] != -1) {
    				map[x][y] += mid / 5;
    				map[r][c] -= mid / 5;
    			}
    		}
    	}
    }
    // 2. 바람으로 미세먼지 이동
    void wind() {
    	// 위쪽 ( 반시계 작업은 거꾸로 수행, 그래야 편함)
    	int i, j, clean_row = clean[0];
    	for (i = clean_row - 2; i >= 0; --i) { // 공기청정기에 들어가면 사라지니까 바로 이전건 그냥 덮어쓰면 됨
    		map[i + 1][0] = map[i][0];
    	}
    	for (j = 1; j < total_col; ++j) {
    		map[0][j - 1] = map[0][j];
    	}
    	for (i = 1; i <= clean_row; ++i) {
    		map[i - 1][total_col - 1] = map[i][total_col - 1];
    	}
    	for (j = total_col - 1; j >= 1; --j) {
    		map[clean_row][j + 1] = map[clean_row][j];
    	}
    	map[clean_row][1] = 0;
    	// 아래쪽 ( 시계 )
    	clean_row = clean[1];
    	for (i = clean_row + 2; i < total_row; ++i) {
    		map[i - 1][0] = map[i][0];
    	}
    	for (j = 1; j < total_col; ++j) {
    		map[total_row - 1][j - 1] = map[total_row - 1][j];
    	}
    	for (i = total_row - 2; i >= clean_row; --i) {
    		map[i + 1][total_col - 1] = map[i][total_col - 1];
    	}
    	for (j = total_col - 2; j >= 1; --j) {
    		map[clean_row][j + 1] = map[clean_row][j];
    	}
    	map[clean_row][1] = 0;
    }
    int main() {
    	int answer, idx = 0;
    	scanf("%d %d %d", &total_row, &total_col, &time);
    	for (int i = 0; i < total_row; ++i) {
    		for (int j = 0; j < total_col; ++j) {
    			scanf("%d", &map[i][j]);
    			if (map[i][j] >= 5) q.push({ i, j, map[i][j] }); 
    		}
    		if (map[i][0] == -1) clean[idx++] = i;
    	}
    	while (time--) {
    		answer = 0;
    		spread();
    		wind();
    		printf("change\n");
    		for (int i = 0; i < total_row; ++i) {
    			for (int j = 0; j < total_col; ++j) {
    				printf("%d ", map[i][j]);
    				if (map[i][j] > 0) answer += map[i][j];
    				if (map[i][j] >= 5) q.push({ i, j, map[i][j] });
    			}
    			printf("\n");
    		}
    	}
    	printf("%d\n", answer);
    	return 0;
    }
  • 바람에 의한 이동 확인용 test case
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    7 8 1
    2 4 0 0 0 0 0 9
    3 0 0 0 3 0 0 8
    -1 3 5 0 0 0 22 0
    -1 8 0 0 0 0 0 3
    3 0 0 0 0 10 43 5
    4 0 5 0 15 0 0 0
    2 1 40 0 0 0 20 3
    // output
    Change
    4 0 0 0 0 0 9 8
    2 0 0 0 3 0 0 0
    -1 0 3 5 0 0 0 22
    -1 0 8 0 0 0 0 0
    4 0 0 0 0 10 43 3
    2 0 5 0 15 0 0 5
    1 40 0 0 0 20 3 0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    6 6 1
     5  0 3  4 1 2
     0  0 7  0 0 3
    -1 10 0 46 0 2
    -1  0 0  0 0 4
     3  0 0  0 0 3
     1  3 1  2 4 2
    change!!
     3 1   4  4 1 2
     1 3   3 10 0 3
    -1 4  12 10 9 2
    -1 2   0  9 0 4
     3 0   0  0 0 3
     1 3   1  2 4 2
백준 17143번 낚시왕|AlgorithmBOJ|Algorithm

#17143. 낚시왕

문제링크

Problem

  • R x C 크기의 격자판
  • 낚시왕 위치 (0, 0)
  • 1초 동안 일어나는 일
    1. 낚시왕 오른쪽으로 한 칸 이동
      (낚시왕이 먼저 이동하기에 상어가 이동하기 전 잡히게 된다.)
    2. 낚시왕이 열에 있는 상어 중 가장 가까운 상어를 잡는다.
    3. 상어 이동
      상어 : 속도와 크기를 가짐
      경계를 넘게되면 방향을 반대로 바꿈
      이동을 마친 후에 상어가 한 칸에 여러 마리 있으면, 가장 큰 상어가 나머지 상어들을 모두 먹음(사라짐)

Goal: 낚시왕이 잡은 상어 크기의 합

  • 입력

    R : ~100
    C : ~100
    M(상어 수) : ~10000
    r, c : 위치 ~R, ~C
    s : 속력 ~1000
    d : 이동방향 1~4 상하우좌
    z : 크기 ~10000

Solution

  • 필자는 인덱스를 0부터 계산하였기에…이를 모두 신경쓰느라 🐕고생
    그냥 1부터 신경쓰는게 편할 수도 있다. (입력 받을 때도 신경써주어야함…)
  • 상어 정보 (MAX는 100)
    1
    2
    3
    4
    struct INFO {
    	int row, col, speed, direction, size;
    	bool death = false;
    }sharks[MAX*MAX];
    상어의 현재 위치, 방향, 크기, 사라졌는지 유무가 저장된다.
    1
    2
    3
    4
    for(열의 수: 처음부터~열의 끝까지 이동) 
    	catchShark() //  1. 상어를 잡는다
    	moveShark() //   2. 상어가 이동한다.
    	updateMap() //   3. 이동을 마친 상어들 map에 반영(먹히면 사라지도록)
  • catchShark()
    해당 열을 탐색하다가 상어를 발견하면 답에 크기를 더해주고 리턴
  • moveShark()
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    주기 : 2 * (전체 행이나 열의 크기-1)
    // ex 방향 -> 전체 열의 크기: 4, 상어는 (1, 2)에 있다고 가정할 때
    위치:     2  3  2  1  0  1  2  3  2  1  0  1  2  3
    방향:    -> <- <- <- -> -> -> <- <- <- -> -> -> <-
    이동거리: 0  1  2  3  4  5  6  7  8  9  10 11 12 13 

    주기가 2 * 3 = 6으로 이동거리가 6마다 같은 위치를 반복하고 있음
    방향은 0이나 전체 열의 크기-1에 위치할 때 바뀜
    위치는 방향에 맞게 이동해주면 됨

    방향
    1 2 3 4  // 상하 우좌
    1 <-> 2 (1일 때 2, 2일 때 1)
    3 <-> 4 (3일 때 4, 4일 때 3)
    현재 방향을 2로 나눴을 때 
    나머지가 0이면 현재 방향에서 1을 빼주고
    아니면 1을 더해주면 바뀐 방향을 구할 수 있다.
  • updateMap()
  1. map을 초기화 해준다. (이동한 상어의 위치를 새로 반영하기 위해)
  2. 해당 위치에 상어가 있을 때와 없을 때를 구분해서 처리를 해준다.

초기에 입력값을 반영하기 위해, 입력을 모두 받고 한 번 호출해준다.

1 Try

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
#include <cstdio>
#define MAX 100
using namespace std;
int r, c, m, idx, answer;
// 상하우좌
int dx[4] = {-1, 1, 0, 0}; 
int dy[4] = {0, 0, 1, -1};
// 상어 정보
struct INFO {
	int row, col, speed, direction, size;
	bool death = false;
}sharks[MAX*MAX];
int map[MAX][MAX][2]; // 상어가 존재한다면 해당 상어 크기와 해당 상어가 몇 번째 상어인지
void catchShark(int col) {
	for (int i = 0; i < r; ++i) {
		if (map[i][col][0] != 0) {
			sharks[map[i][col][1]].death = true;
			answer += sharks[map[i][col][1]].size;
			return;
		}
	}
}
void changeDirection(int idx) {
	if (sharks[idx].direction % 2 == 0) {
		sharks[idx].direction--;
	}
	else {
		sharks[idx].direction++;
	}
}
void moveShark(int idx, int end) {
	int period = 2 * end;
	int move = sharks[idx].speed % period;
	for (int i = 0; i < move; ++i) {
		if (sharks[idx].direction <= 2) { // 상하
			if ((sharks[idx].row == end && sharks[idx].direction == 2) ||
				(sharks[idx].row == 0 && sharks[idx].direction == 1)) {
				changeDirection(idx);
			}
			sharks[idx].row += dx[sharks[idx].direction - 1];
		}
		else { // 우좌
			if ((sharks[idx].col == end && sharks[idx].direction == 3) ||
				(sharks[idx].col == 0 && sharks[idx].direction == 4)) {
				changeDirection(idx);
			}
			sharks[idx].col += dy[sharks[idx].direction-1];
		}
	}
}
void updateMap() {
	for (int i = 0; i < r; ++i) { // map 초기화
		for (int j = 0; j < c; ++j) {
			map[i][j][0] = 0;
		}
	}
	for (int i = 0; i < m; ++i) {
		if (sharks[i].death) continue;
		int r = sharks[i].row;
		int c = sharks[i].col;
		if (map[r][c][0] != 0) { // 해당 위치에 상어가 있다면
			if (sharks[i].size > map[r][c][0]) {
				sharks[map[r][c][1]].death = true;
				map[r][c][0] = sharks[i].size;
				map[r][c][1] = i;
			}
			else {
				sharks[i].death = true;
			}
		}
		else { // 해당 위치에 상어가 없을 때
			map[r][c][0] = sharks[i].size;
			map[r][c][1] = i;
		}
	}
}

int main() {
	scanf("%d %d %d", &r, &c, &m);
	int row, col;
	for (int i = 0; i < m; ++i) {
		scanf("%d", &row);
		sharks[idx].row = row - 1;
		scanf("%d", &col);
		sharks[idx].col = col - 1;
		scanf("%d", &sharks[idx].speed);
		scanf("%d", &sharks[idx].direction);
		scanf("%d", &sharks[idx++].size);
	}
	updateMap(); // 초기 map update
	for (int i = 0; i < c; ++i) {
		catchShark(i); // 상어 잡기
		for (int j = 0; j < m; ++j) { // 상어 이동
			if (sharks[j].death) continue;
			if (sharks[j].direction <= 2) {
				moveShark(j, r-1);
			}
			else {
				moveShark(j, c-1);
			}
		}
		updateMap(); // 이동한 상어 위치 반영
	}
	printf("%d\n", answer);
	return 0;
}
  • 자꾸 for문에서 i나 j가 아닌 r, c로 고정값을 두어서…이런 실수는 진짜진짜 조심하자.

For Debug

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
#include <cstdio>
#define MAX 100
using namespace std;
int r, c, m, idx, answer;
// 상하우좌
int dx[4] = {-1, 1, 0, 0}; 
int dy[4] = {0, 0, 1, -1};
// 상어 정보
struct INFO {
	int row, col, speed, direction, size;
	bool death = false;
}sharks[MAX*MAX];
int map[MAX][MAX][2]; // 상어가 존재한다면 해당 상어 크기와 해당 상어가 몇 번째 상어인지
void catchShark(int col) {
	/*printf("%d번째\n", col); // map 확인
	for (int i = 0; i < r; ++i) {
		for (int j = 0; j < c; ++j) {
			printf("%d ", map[i][j][0]);
		}
		printf("\n");
	}*/
	for (int i = 0; i < r; ++i) {
		if (map[i][col][0] != 0) {
			sharks[map[i][col][1]].death = true;
			answer += sharks[map[i][col][1]].size;
			return;
		}
	}
}

void changeDirection(int idx) {
	if (sharks[idx].direction % 2 == 0) {
		sharks[idx].direction--;
	}
	else {
		sharks[idx].direction++;
	}
}

void moveShark(int idx, int end) {
	int period = 2 * end;
	int move = sharks[idx].speed % period;
	for (int i = 0; i < move; ++i) {
		if (sharks[idx].direction <= 2) { // 상하
			if ((sharks[idx].row == end && sharks[idx].direction == 2) ||
				(sharks[idx].row == 0 && sharks[idx].direction == 1)) {
				changeDirection(idx);
			}
			sharks[idx].row += dx[sharks[idx].direction - 1];
		}
		else { // 우좌
			if ((sharks[idx].col == end && sharks[idx].direction == 3) ||
				(sharks[idx].col == 0 && sharks[idx].direction == 4)) {
				changeDirection(idx);
			}
			sharks[idx].col += dy[sharks[idx].direction-1];
		}
	}
}

void updateMap() {
	for (int i = 0; i < r; ++i) {
		for (int j = 0; j < c; ++j) {
			map[i][j][0] = 0;
		}
	}
	for (int i = 0; i < m; ++i) {
		if (sharks[i].death) continue;
		int r = sharks[i].row;
		int c = sharks[i].col;
		if (map[r][c][0] != 0) { // 해당 위치에 상어가 있다면
			if (sharks[i].size > map[r][c][0]) {
				sharks[map[r][c][1]].death = true;
				map[r][c][0] = sharks[i].size;
				map[r][c][1] = i;
			}
			else {
				sharks[i].death = true;
			}
		}
		else { // 해당 위치에 상어가 없을 때
			map[r][c][0] = sharks[i].size;
			map[r][c][1] = i;
		}
	}
}

int main() {
	scanf("%d %d %d", &r, &c, &m);
	int row, col;
	for (int i = 0; i < m; ++i) {
		scanf("%d", &row);
		sharks[idx].row = row - 1;
		scanf("%d", &col);
		sharks[idx].col = col - 1;
		scanf("%d", &sharks[idx].speed);
		scanf("%d", &sharks[idx].direction);
		scanf("%d", &sharks[idx++].size);
	}
	updateMap();
	/*for (int i = 0; i < m; ++i) { // 입력 확인
		printf("%d %d %d %d %d\n", sharks[i].row, sharks[i].col, sharks[i].speed, sharks[i].direction, sharks[i].size);
	}*/
	for (int i = 0; i < c; ++i) {
		catchShark(i);
		for (int j = 0; j < m; ++j) {
			if (sharks[j].death) continue;
			if (sharks[j].direction <= 2) {
				moveShark(j, r-1);
			}
			else {
				moveShark(j, c-1);
			}
		}
		updateMap();
	}
	printf("%d\n", answer);
	return 0;
}
백준 17142번 연구소 3|AlgorithmBOJ|Algorithm

#17142. 연구소 3

Problem

Solution

  • 퍼트릴 M개의 바이러스를 선택한다. (DFS)
    중복을 허용하지 않는 조합이다.
  • 선택한 바이러스를 퍼트리다. (BFS)
    4 방향으로 탐색을 하되, 빈 칸 또는 바이러스가 있는 곳이어야 한다.
  • dist라는 배열에 시간을 저장한다.
    단, 모서리에 있는 바이러스에서 탐색이 끝난 경우 시간을 1 빼주어야 한다.

1 Try

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
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int N, M, ans = 1e9;
int map[50][50];
int selected[10];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
vector<pair<int, int>> virus;
void Spread() {
	bool visit[50][50] = { 0, };
	int dist[50][50] = { 0, };
	queue<pair<int, int>> q;
	for (auto e : selected) {
		if (e != -1) {
			q.push({ virus[e].first, virus[e].second });
			visit[virus[e].first][virus[e].second] = true;
		}
	}
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int dir = 0; dir < 4; ++dir) {
			int d_x = x + dx[dir];
			int d_y = y + dy[dir];
			if (d_x < 0 || d_y < 0 || d_x >= N || d_y >= N) continue;
			if (map[d_x][d_y] == 1 || visit[d_x][d_y]) continue;
			visit[d_x][d_y] = true;
			q.push({ d_x, d_y });
			dist[d_x][d_y] = dist[x][y] + 1; 
		}
	}
	int time = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (dist[i][j] != 0 && map[i][j] == 2) {
				if (i == 0 || j == 0 || i == N - 1 || j == N - 1)
					dist[i][j]--;
			}
			if (!visit[i][j] && map[i][j] == 0) return;
			if (dist[i][j] > time) time = dist[i][j];
		}
	}
	if (ans > time) ans = time;
}
void SelectVirus(int idx, int cnt) {
	if (cnt == M) {
		Spread();
		return;
	}
	for (int i = idx; i < virus.size(); ++i) {
		selected[i] = i;
		SelectVirus(i+1, cnt + 1);
		selected[i] = -1;
	}
}
int main() {
	cin >> N >> M;
	bool no_zero = true;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> map[i][j];
			if (map[i][j] == 2) virus.push_back({ i, j });
			if (map[i][j] == 0) no_zero = false;
		}
	}
	if (no_zero) {
		cout << 0 << "\n";
	}
	else {
		memset(selected, -1, sizeof(selected));
		SelectVirus(0, 0);
		if (ans != 1e9) cout << ans << "\n";
		else cout << -1 << "\n";
	}
	return 0;
}
백준 17140번 이차원 배열과 연산|AlgorithmBOJ|Algorithm

#17140. 이차원 배열과 연산

Problem

Solution

  • 시뮬레이션 문제이다. (항상 자료구조를 뭘 사용할지 잘 판단하자.)
  • 여기서는 map과 priority queue를 사용하였다.
  • map의 쓰임

<수, 등장 횟수>를 저장하기 위해 쓰인다. 처음에 1차원 배열로 cnt[수]=등장 횟수로 하려 했지만, 이렇게 되면 매번 100번 for문을 연산해야 한다고 느껴 map을 이용해 바로 접근이 가능하도록 하였다.

  • priority queue의 쓰임

R연산 또는 C연산 중에 생성되는 정렬된 값들을 저장하기 위해 쓰인다. 연산자를 오버로딩하여 삽입 시 정렬 순위를 정해주었다.
원래 우선순위 큐는 기본적으로 내림차순으로 정렬되어 있다. (pair라면 첫 번째 기준, 첫 번째 원소가 같다면 두 번째 원소 내림차순 정렬)

그렇기에 따로 정해주었는데 그럴 필요 없이 -를 붙여 저장하면 오름차순으로 정렬된다는 것을 깨닫고…(유레카!!)

*아래 코드는 그러진 않았다.

  • 해당 수를 카운트할 때 중요한 것은 카운트가 끝나면 해당 배열의 값을 0으로 바꾼다는 것이다. 그래야 행이나 열의 크기가 줄어들 때 영향을 받지 않고 연산을 정상적으로 수행할 수 있다.
  • 그 외는 문제 그대로 구현하면 된다.

1 Try

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 <queue>
#include <map>
using namespace std;
int r, c, k, total_r, total_c;
int A[100][100]; // 1 ~ 100
map<int, int> cnt;
struct Info {
	int num, count;
};
bool operator<(const Info &v1, const Info &v2) {
	if (v1.count == v2.count) return v1.num > v2.num;
	return v1.count > v2.count;
}
void Input() {
	cin >> r >> c >> k;
	total_r = total_c = 3;
	for (int i = 0; i < total_r; ++i) {
		for (int j = 0; j < total_c; ++j) {
			cin >> A[i][j];
		}
	}
}
void Task() {
	for (int t = 0; t <= 100; ++t) {
		if (A[r - 1][c - 1] == k) {
			cout << t << "\n";
			return;
		}
		priority_queue<Info> pq;
		if (total_r >= total_c) { // R 연산
			for (int i = 0; i < total_r; ++i) {
				for (int j = 0; j < total_c; ++j) {
					if (A[i][j] == 0) continue;
					if (cnt.count(A[i][j]) == 0) cnt[A[i][j]] = 1;
					else cnt[A[i][j]]++;
					A[i][j] = 0;
				}
				for (auto e : cnt) {
					pq.push({ e.first, e.second });
				}
				cnt.clear();
				int len = pq.size() * 2;
				for (int j = 0; j < len; j += 2) {
					A[i][j] = pq.top().num; A[i][j + 1] = pq.top().count;
					pq.pop();
				}
				if (total_c < len) total_c = len;
			}
		}
		else { // C 연산
			for (int i = 0; i < total_c; ++i) {
				for (int j = 0; j < total_r; ++j) {
					if (A[j][i] == 0) continue;
					if (cnt.count(A[j][i]) == 0) cnt[A[j][i]] = 1;
					else cnt[A[j][i]]++;
					A[j][i] = 0;
				}
				for (auto e : cnt) {
					pq.push({ e.first, e.second });
				}
				cnt.clear();
				int len = pq.size() * 2;
				for (int j = 0; j < len; j += 2) {
					A[j][i] = pq.top().num; A[j + 1][i] = pq.top().count;
					pq.pop();
				}
				if (total_r < len) total_r = len;
			}
		}
	}
	cout << -1 << "\n";
}
int main() {
	Input();
	Task();
	return 0;
}