대엉코딩

www.acmicpc.net/problem/11404

1. 풀이방법

- 문제를 읽다보면 문제에서는 버스, 즉 간선(단방향)이 비용(가중치)를 각각 가지고 있다.

- (->BFS로는 구할 수 없겠구나 ! 라는 생각)

- 다익스트라 또는 플로이드 워셜 (대표적)

- 근데 출력을 보니 모든 도시에서 자신을 제외한 모든 점까지의 최단거리를 출력하는 문제 (자신 또는 못가는 경우 0 )

- (-> 플로이드 워셜 ! )

2. 주의사항

- 구현 시 도시사이의 거리를 입력 받기전 가장 큰 값으로 초기화 해줘야 하는데 COST가 100,000을 넘지 않는 다는 말을

- 보고 100001으로 정의해두었다가(INF) 계쏙 98퍼에서 오류가 뜨길래...생각해보니...

- 거쳐서 가는경우 100,000을 그냥 넘을 수 있다는 것......!!! 주의주의.... 그래서 그냥 987654321로 초기화 하였다

3. 나의코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define INF 987654321

int n, m;
int CityToCity[101][101];

void inputs() { //입력함수
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) { //초기화
			if (i == j) continue;
			CityToCity[i][j]=INF;
		}
	}
	int start, end, cost;
	for (int i = 0; i < m; i++) {
		cin >> start >> end >> cost;
		if (CityToCity[start][end] > cost) {
			CityToCity[start][end] = cost;
		}
	}
}

void Searchmin() {
	for (int a = 1; a <= n; a++) {
		for (int b = 1; b <= n; b++) {
			for (int c = 1; c <= n; c++) {
				if (CityToCity[b][a] != INF && CityToCity[a][c] != INF) { //거쳐서 갈 수 있는 경우
					CityToCity[b][c] = min(CityToCity[b][c], (CityToCity[b][a] + CityToCity[a][c]));
				}
			}
		}
	}
}
void outputs() { //출력함수
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (CityToCity[i][j] == INF||i==j)  cout << 0 << " "; 
			else cout << CityToCity[i][j] << " ";
		}
		cout << "\n";
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	inputs();
	Searchmin();
	outputs();
	return 0;
}

www.acmicpc.net/problem/16234

1. 풀이방법

- 조건이 조금 많긴 하지만 하나씩 처리하면 구현자체가 많이 어렵지는 않습니다..

- while문 안 쪽에서 dfs를 통해서 구역들을 연결해주며 peoplesum에 인구수의 합을 저장하고, nationcount에 구역의 수를 저장.

-그리고 나중에 인구수의합/구역의 수 로 각 연결된 구역의 값을 초기화 해주어야하는데 dfs를 이용했으므로 저는

따로 vector를 선언해서 x,y를 저장해 놓은 뒤 배정 해두었으나....지금 생각해보니 dfs 수행 부 뒤쪽에서 초기화를 해줘도 될 것으로 보이네요....! 이런......!

-백준 알고리즘 사이트에서는 이 문제의 분류를 너비우선탐색으로 기재해놓았던데, bfs로 구현할 수 있을 것 같긴 하지만 문제에서 주는 뉘앙스는 뭔가 dfs에 더 가까운 듯한 개인적인 느낌입니다.

2. 주의사항

- 조건을 꼼꼼히 살필 것.

- 방문(visited) 배열을 초기화 해주는 작업이 필요하다(인구수 이동이 일어난 이후, 다음 인구수 이동이 일어나기 전에)

3. 나의 코드

#include<iostream>
#include<vector>
using namespace std;

int N, L, R;
int ground[51][51];
int visited[51][51];//방문여부 체크
int dx[4] = { 0,0,-1,1 }; //4방향 탐색
int dy[4] = { 1,-1,0,0 };
int peoplesum = 0; //구역의 인구수 합
int nationcount = 0; // 구역의 수
int resultcount; //몇번의 인구이동
bool finish = false; //인구이동이 한번이라도 일어났는지를 체크하기 위한
vector<pair<int, int>> node; //연결된 구역들의 위치를 저장해두기 위한 벡터
pair<int, int> tmp; //임시벡터
 
void inputs() { //입력함수
	cin >> N >> L >> R;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> ground[i][j];
		}
	}
}
int gapabs(int num1, int num2) { //인구수 차이를 리턴
	if (num1 > num2) return (num1 - num2);
	else return (num2 - num1);
}
void searchmove(int i,int j) { //dfs 수행부
	visited[i][j] = true;
	for (int k = 0; k < 4; k++) {
		if (i + dx[k] >= 0 && i + dx[k] < N&&j + dy[k] >= 0 && j + dy[k] < N&&visited[i+dx[k]][j+dy[k]]==false) {//방문하지 않았고, 지도 내부
			if (gapabs(ground[i][j], ground[i + dx[k]][j + dy[k]]) >= L && gapabs(ground[i][j], ground[i + dx[k]][j + dy[k]]) <= R) { //L이상 R이하인 경우만
				finish = true; //한번이라도 인구수 이동이 이동이 일어난 경우 ---> 종료조건을 위한...!!
				nationcount += 1;
				peoplesum += ground[i + dx[k]][j + dy[k]];
				tmp.first = i+dx[k]; tmp.second = j+dy[k];
				node.push_back(tmp);
				searchmove(i + dx[k], j + dy[k]); //dfs수행
			}
		}
	}
}
void initvisited() { //방문배열을 초기화 (인구이동 발생 후 초기화해주어야 함)
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			visited[i][j] = false;
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	inputs();
	while (1) { //한번의 인구이동마다 while 내부 수행
		finish = false;
		initvisited();//방문배열 초기화
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (visited[i][j] == false) {
					node.clear();
					nationcount = 1;
					peoplesum = ground[i][j];
					tmp.first = i; tmp.second = j;
					node.push_back(tmp); //나중에 인구수 조정을 해줘야 하므로 x,y좌표를 벡터에 넣어놓는다.
					searchmove(i, j);//dfs 수행
					if(finish==true){
						for (int i = 0; i < node.size(); i++) { //총 구역의 인구수/구역의수 를 각각 x,y,를 저장해놓았던 구역에 넣어준다.
							ground[node[i].first][node[i].second] = peoplesum / nationcount;
					}
				}
				}
			}
		}
		if (finish == false) { cout << resultcount; break; }
		else { resultcount++; }
	}
	return 0;
}

www.acmicpc.net/problem/18405

1. 풀이방법

- 전형적인 bfs문제 입니다.

- 문제만 읽어봐도 느낌이 딱 오는데, 하나의 조건이 있습니다.

- 바로 매번 번식을 하기는 하는데, 번호가 낮은 바이러스가 먼저 번식을 시작한다는 것.....!

- 그래서 처음에는 큐를 이용하여 구현을 할까 하다가

- 벡터를 이용해서 구현한 뒤, 오름차순 정렬을 하여 앞 쪽 바이러스부터 감염이 시작되도록 하였습니다.

2. 주의사항

- 번호가 낮은 바이러스 부터 번식을 시작한다는 것.

- 문제 조건 꼼꼼히 파악.

3. 나의코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int N, K;
int S, X, Y;
int virusmap[201][201];
bool viruscheck[201][201];
int dx[4] = { 0,0,1,-1 }; //4방향 탐색을 위한
int dy[4] = { 1,-1,0,0 };
struct vi { int x; int y; int num; }; //바이러스 좌표와 number를 저장하는 구조체
vector<vi> tmparr; //1초마다 4방향 탐색을 진행해야하는 후보?바이러스들을 담은 set

void inputs() { //입력함수
	cin >> N >> K; 
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> virusmap[i][j];
			if (virusmap[i][j] != 0) {
				viruscheck[i][j] = true;
			}
		}
	}
	cin >> S >> X >> Y;

}
bool cmp(vi a, vi b) { //바이러스 번호 순 정렬을 위한 비교함수
	if (a.num < b.num) return true;
	else return false;
}
void startinfection(int x, int y) { //4방향 탐색
	for (int i = 0; i < 4; i++) {
		if (x+dx[i]>=0&&x+dx[i]<N&&y+dy[i]>=0&&y+dy[i]<N&&viruscheck[x+dx[i]][y+dy[i]] == false) {
			virusmap[x + dx[i]][y + dy[i]] = virusmap[x][y];
			viruscheck[x + dx[i]][y + dy[i]] = true;
		}
	}
}
void makeascvirusset() { //바이러스map을 탐색해서 바이러스를 set에 넣어둔다
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (virusmap[i][j] != 0) {
				vi tmp;
				tmp.x = i; tmp.y = j; tmp.num = virusmap[i][j];
				tmparr.push_back(tmp);
			}
		}
	}
}
void searchvirus(int s, int x, int y) {
	int second = 0;
	while (1) {
		if (virusmap[x-1][y-1] != 0) { cout << virusmap[x-1][y-1]; break; } //이미 번식하고 있는 바이러스가 있으면 거기에 다른 바이러스가 올수 없으므로 바로 출력
		if (second == s) { cout << 0; break; } //시간에 맞았는데 위에 if문에 안 걸렸다는 뜻이므로 0 출력
		tmparr.clear();
		makeascvirusset();
		sort(tmparr.begin(), tmparr.end(), cmp); //set을 정렬한다(오름차순) 낮은 바이러스부터 번식을 시작하므로
		for (int i = 0; i < tmparr.size(); i++) {
			startinfection(tmparr[i].x, tmparr[i].y);
		}
		second++;
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	inputs();
	searchvirus(S, X, Y);
	return 0;
}

www.acmicpc.net/problem/17471

1.풀이 방법.

- 분류는 dfs로 하였다. (dfs를 통해서 연결된 같은 선거구를 탐색하였고)

- 선거구 1의 첫번째 구역을 기준으로 dfs를 한번 돌리고 , 선거구2의 첫번째 구역을 기준으로 dfs를 한번 수행했다.

- 그랬을때 방문을 체크하는 배열 check의 각 구역은 모두 true로 되어있어야 각 선거구가 모두 연결되어 있다는

뜻이다. (전 그렇게 체크하였습니다.)

- 처음에 조합을 만들어서(단 수의 제한이 없음 N개의 지역을 모두 선거구 1이 가져가는 것만 거르면 됨)

CASE를 만들어서 계산에 들어갔고 들어가서 선거구 2에 선거구1에 포함되지 않은 구역들을 넣어주어서

- 일단 CASE에 대한 선거구1,선거구2를 나누어 주었고 DFS를 돌려 연결되어있는지 확인후.

- 나누어진 선거구가 각자 모두 연결되어있다는 것이 확인되면 인구수의 합의 차이를 결과벡터에

삽입 해주고 소팅 후 최소값을 출력하였습니다.

2. 주의사항

- 전략을 처음에 세우고 들어갔는데..... 노트와 펜으로 세운 전략은 이랬습니다.

-<노트에 쓴 내용>

1. CASE를 만들자(분류) 

2. DFS로 각 CASE가 유효한 CASE인지 확인하자(모두 각자 연결되어 있는지)

3. 인구수 차이를 측정

- 이렇게 세우고 코드를 작성하러 들어갔는데

- 순차적으로 짜다보니 코드가 매우 길어졌습니다.

- 그리고 전역변수에 대한 각 작업 수행시 초기화가 필요한 경우 추가로 함수를 작성하고 하다보니..

  더 길어졌는데.....전략 뿐만아니라 조금 더 명확한 틀을 설정하려고 노력해야겠습니다.....

(코드가 길어지면 짜다 보면 막 헷갈리는 부분이 생기고 갑자기 멍해지기도 하고....;;)

3.나의코드

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

bool check[11]; //방문한 노드인지 확인
int groupindex[11]; //CASE별 각 구역이 어떤 선거구에 포함되어있는지 확인
vector<int> edges[11]; //연결된 간선 정보 저장
int peoplecount[11]; //각 구역별 인구수 저장변수
int tmp;
int N;
vector<int> votecamp1; //선거구1에 해당하는 구역을 담을 벡터
vector<int> resultmin;//각 CASE별 인구 수 차이를 담아놓을 변수

void input() {//입력받는 함수
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> peoplecount[i];
	}
	for (int i = 1; i <= N; i++) {
		cin >> tmp;
		for (int j = 0; j < tmp; j++) {
			int n; cin >> n;
			edges[i].push_back(n);
		}
	}

}
int getsum(vector<int> arr) { //인구수 합 구하는 함수
	int s = 0;
	for (int i = 0; i < arr.size(); i++) {
		s += peoplecount[arr[i]];
	}
	return s;
}
void resetcheck() { //초기화함수
	for (int i = 0; i < 11; i++) {
		check[i] = false;
	}
}
int gap(int num1, int num2) { //단순히 차이를 리턴하는 함수
	if (num1 > num2) { return (num1 - num2); }
	else { return (num2 - num1); }
}
void dfs(int index,int g) { //DFS수행
	check[index] = true;
	for (int i = 0; i < edges[index].size(); i++) {
		if (check[edges[index][i]]==false&&groupindex[edges[index][i]] == g) {
			//방문하지 않았고, 나와 같은 선거구 인 경우 탐색을 수행
			dfs(edges[index][i],g);
		}
	}
	return;
}
bool all() { //모두 방문했는지 체크를 위한 함수
	for (int i = 1; i <= N;i++) {
		if (check[i] == false) return false;
	}
	return true;
}
void groupindexreset() { //초기화 함수
	for (int i = 0; i < 11; i++) {
		groupindex[i] = 1;
	}
}
void checkvotecamp() {
	if (votecamp1.size() == N) { return; }
	vector<int> votecamp2; //선거구2를 담을 변수
	groupindexreset(); //각 지역이 어떤 선거구에 속했는지를 담을 변수 초기화
	for (int i = 1; i <= N; i++) { //1에 속하지 않은 지역은 2에 넣기
		bool c = false;
		for (int j = 0; j < votecamp1.size(); j++) {
			if (votecamp1[j] == i) { c = true; break; }
		}
		if (c == false) { votecamp2.push_back(i);
		groupindex[i] = 2;
		}
	}
	resetcheck();
	dfs(votecamp1[0],1); //선거구의 지역이 모두 연결되어있는지 체크를 위해 DFS
	dfs(votecamp2[0],2);
	if (all() == true) {
		int first = getsum(votecamp1);
		int second = getsum(votecamp2);
		resultmin.push_back(gap(first, second));
	}

}
void makecase(int num) { //조합CASE(수가 정해지지 않은)
	if (num > N) { return; }
	for (int i = num; i <= N; i++) {
		votecamp1.push_back(i);
		checkvotecamp();
		makecase(i + 1);
		votecamp1.pop_back();
	}
}
int main() {
	// 1 ~ N 의 구역
	input(); //입력
	makecase(1); //케이스 만들자
	sort(resultmin.begin(), resultmin.end()); //최소값 출력 부
	if (resultmin.empty()) { cout << -1; return 0; }
	cout << resultmin[0];
	return 0;
}

www.acmicpc.net/problem/18352

1. 풀이방법

- 일단 N의 개수가 300,000이므로 굉장히 큽니다.

- 이차원배열을 고정으로 선언할 경우 작동이 안됩니다.

- 따라서 vector를 이용하여 vector[x].push_back(y) --> x에서가는 y에대해 가는 간선이 있다는 정보저장

- 조건 중 중요한것은 간선의 가중치가 모두 1이라는 것....!  --->이게 있으므로 bfs를 수행하여 최단거리를 구할 수 있다  고 생각 할 수 있습니다.

- 최단거리로 가는 도시들만 출력해야 하므로 visited 배열을 통해 방문한 노드인지 체크를 하며 bfs를 수행하면 됩니다.

- 큐를 이용했고 거리만큼의 bfs를 수행한 후에는 벡터에 옴겨 sorting을 해서 차례로 출력하여 주었습니다.

2. 주의사항

- 조건상에서 왜 bfs를 수행해서 구할 수 있는지 파악 (정당성)

3. 나의 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

queue<int> tmpqueue;
vector<int> edge[300001]; //간선정보저장
bool visited[300001]; //방문정보 저장
int N, M, K, X;
int loadlength;

void inputedge() { //간선정보를 저장
	int x, y;
	for (int i = 0; i < M; i++) {
		cin >> x >> y;
		edge[x].push_back(y);
	}
}

void resultoutput() { //오름차순 정렬 (큐에서 벡터로 옴겨서)
	vector<int> resultsave;
	while (tmpqueue.empty()!=true) {
		resultsave.push_back(tmpqueue.front());
		tmpqueue.pop();
	}
	sort(resultsave.begin(), resultsave.end());
	for (int i = 0; i < resultsave.size(); i++) {
		cout << resultsave[i] << "\n";
	}
}

void bfs(int X) {
	tmpqueue.push(X);
	visited[X] = true;
	while (1) {
		if (tmpqueue.empty()) { cout << -1 << "\n"; break; }
		if (loadlength == K) { resultoutput(); break; }
		int qsize = tmpqueue.size();
		while(qsize--){
			int startnode = tmpqueue.front();
			for (int i = 0; i < edge[startnode].size(); i++) {
				if (visited[edge[startnode][i]] == false) {
					tmpqueue.push(edge[startnode][i]);
					visited[edge[startnode][i]] = true;
				}
			}
			tmpqueue.pop();
		}
		loadlength++;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> K >> X;
	inputedge();
	bfs(X);

	return 0;
}

몇개의 조건이 달린 dfs 이용 문제입니다.

while문 안에서 물의 높이를 1씩 증가 시켜가면서 

dfs를 돌려 침수영역을 구하고 기존의 최대 침수 지역을 넘는 수 라면 그 수를 최대침수지역에 넣습니다.

모든 지역이 모두 침수 되었을 경우 break문을 걸어 while문 을 빠져 나오고 

출력을 하였습니다.

(코로나 때문에 학사일정이 너무 정신없어서 간만에 문제를 풀었더니 깔끔하지가 않은 느낌이네요...)

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

- 기본적인 dfs 문제입니다. 

- 문제를 읽으면 dfs구나 알 수 있고 처음 접해서 풀기 좋은 문제인 것 같습니다.

- 좌표 기준 때문에 i,j만 조금 신경써서 해주시면 됩니다(문제에 맞추어서)

- 전 항상 몇번 풀어도 좌표 기준 신경 쓰는게 그렇게 짜증나더라는...ㅎ;;;

<필기>

<코드>

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

이차원 배열을 통해서 map을 그리고 벽을 3개만 칠 수 있는데 벽을 3개를

쳤을 때 안전영역(바이러스가 퍼지지않는) 을 최대로 만들어 그 최대값을 출력하는 문제입니다.

초반에 어떠한 규칙을 세워야 좋을까 생각이 들었지만 너무 경우의 수가 많아 딱히

적용되는 규칙을 찾기 힘들어 모든 경우의 수를 다 세우고 그 경우의 수에 따라서 안전영역의 값을

구해 봐야되나....? 라는 생각을 한후 그럴경우 입력값의 조건들이 너무 크면 안되기 때문에 그를

확인해보니 (3<=N.M<=8) 이라 작은값임을 확인하고 그로 방향을 잡아 풀었습니다.

저는 [10][10] 배열을 만들어 index 0과9는 1로 채워서 벽같은 느낌을 주었습니다(바이러스가 퍼지지 못하게)

물론  조건문에 index를 걸어도 되지만 귀찮아서.....

아 그리고 벽이 세워질 수 있는 지역은 좌표를 구조체로 설정하여

벡터(vector)에다가 모두 넣은 다음 그 벡터에서 3개씩을 골라서 그 3개에 벽이 세워졌을 때 안전구역을 구하였습니다.

bfs를 통해서 -- 더이상 바이러스가 퍼질 구역이 없어서 큐가 비어있게 될경우 탐색을 멈춤

3중 반복문 이용(완전탐색) -- 이 과정에서 조건수정을 하느라고 시간이 좀 걸렸습니다.

<코드>