이것 저것 &

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

최단거리 탐색을 할때는 bfs 알고리즘을 사용합니다.

보물위치의 최단거리를 출력하는 문제였습니다. 

어느지점을 기준으로 출발하느냐에 따라 결과가 달라지기에 조금 생각해야하는 문제였습니다.

근데 높이,너비가 50까지임으로 저는 모든점에서의 최장거리를 계산해서 문제의 답을 구했습니다.

한가지 예외처리를 못했던 테스트케이스입니다.

4 4

LLWW

WWWW

WWWW

WWWW

이경우 1이 나와야하지만 

간혹 2가 나오는 코드들이 있습니다.

조건문에 (a!= y + de_y[i] || b != x + de_x[i])를 추가해줌으로써 해결했습니다. (출발지점으로 되돌아 오면 안되기 때문에)

기존의 bfs문제들을 풀어보셨다면 쉬운문제였을겁니다.

정답코드입니다. 직접 손으로 작성해보세요 :) 화이팅

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int height, width;

string arr[51];
int visited[51][51];
int que[2501][2];
int started,ended;
int de_x[4] = { 1, 0, 0,-1 };
int de_y[4] = { 0, 1,-1, 0 };
int result = 0;

void bfs(int a, int b) {
	started = 0, ended = 0;
	que[ended][0] = a;
	que[ended][1] = b;
	ended++;

	while (started != ended) {
		int y = que[started][0];
		int x = que[started++][1];
		
		for (int i = 0; i < 4; i++) {
			if ((y + de_y[i])>=0 && (y + de_y[i])<height && (x + de_x[i])>=0 && (x + de_x[i])<width)
				if (arr[y + de_y[i]][x + de_x[i]] == 'L' && !visited[y + de_y[i]][x + de_x[i]] && (a!= y + de_y[i] || b != x + de_x[i]))
				{
					visited[y + de_y[i]][x + de_x[i]] = visited[y][x] + 1;
					que[ended][0] = y + de_y[i];
					que[ended++][1] = x + de_x[i];
					
				}

		}
		
	}

	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			if (arr[i][j] == 'W') continue;
			if (result < visited[i][j] ) result = visited[i][j];
		}
	}


}
int main() {

	cin >> height >> width;
	for (int i = 0; i < height;i++)
		cin >> arr[i];

	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			if (arr[i][j] == 'W') continue;
			memset(visited, 0, sizeof(visited));
			
			bfs(i,j);


		}
	}

	cout << result << endl;
}

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

처음에 보자마자 생각난건 union-find 알고리즘이였다. 서로 친척인지 확인을 해주기 위한 방법으로 사용하였다.

그이후에는 몇가지 케이스를 대입보면서 촌수계산을 분명하게 하기위해서는 완전탐색을 해야하는 것을 깨닭았고,

dfs와 bfs중에 고민하였다. 아마 dfs로도 풀이가 가능할 것이다. 탐색에 좀 더 적합한 bfs를 선택했다.

1. search_root() 함수를 통해서 서로 친척인지 확인 

2. 출발점x로부터 y까지 도달하는 과정에서 각 값들을 큐에 저장하며 해당 직계도를 탐색

3. bfs함수 호출이 끝난후 cnt[y]값을 출력 ( 전달받아 오면서 값이 +1씩 증가했으므로 촌수와 동일)

bfs에서 !visited[arr[i][1]] 의 조건은 최소의 촌수를 선택해야하기 때문입니다. 

정답코드입니다. 

#include <iostream>
using namespace std;
int n = 0, m = 0, x, y,a,b;
int arr[101][2] = { 0 };
int root_x, root_y;
int cnt[101] = { 0 };
bool visited[101] = { 0 };

void bfs() {

	int que[101] = { 0 };
	int started = 0, ended = 0;

	que[ended++] = x;

	while (started != ended) {
		int val = que[started++];
		visited[val] = 1;

		for (int i = 0; i < m; i++) {
			if (arr[i][0] == val && !visited[arr[i][1]]) {
				
				que[ended++] = arr[i][1];
				cnt[arr[i][1]] = cnt[val] + 1;
			}

			if (arr[i][1] == val && !visited[arr[i][0]]) {
				
				que[ended++] = arr[i][0];
				cnt[arr[i][0]] = cnt[val] + 1;
			}

		}


	}

}


void search_root() {

	root_x = x;
	root_y = y;

	while (1) {
		bool t = false, r = false;
		for (int i = 0; i < m; i++) {
			if (arr[i][1] == root_x) {
				t = true;
				root_x = arr[i][0];

			}
			if (arr[i][1] == root_y) {
				r = true;
				root_y = arr[i][0];
			}
		}
		if (t == false && r == false)
			break;
	}
}


int main() {
	cin >> n;
	cin >> x >> y;
	cin >> m;
	for (int i = 0; i < m; i++)
		cin >> arr[i][0]>>arr[i][1];
	
	search_root();
	if (root_x != root_y) {
		cout << -1 << endl;
		return 0;
	}

	bfs();

	cout << cnt[y] << endl;

}

움.. 그런데... 생각해보니 searchroot가 필요가 없죠? 어차피 탐색이 안되면 cnt[y]값을 0일 것이기 때문에 그때만 -1로 출력을 해주면 되기 때문입니다.

수정답안 입니다.

#include <iostream>
using namespace std;
int n = 0, m = 0, x, y,a,b;
int arr[101][2] = { 0 };
int root_x, root_y;
int cnt[101] = { 0 };
bool visited[101] = { 0 };

void bfs() {

	int que[101] = { 0 };
	int started = 0, ended = 0;

	que[ended++] = x;

	while (started != ended) {
		int val = que[started++];
		visited[val] = 1;

		for (int i = 0; i < m; i++) {
			if (arr[i][0] == val && !visited[arr[i][1]]) {
				
				que[ended++] = arr[i][1];
				cnt[arr[i][1]] = cnt[val] + 1;
			}

			if (arr[i][1] == val && !visited[arr[i][0]]) {
				
				que[ended++] = arr[i][0];
				cnt[arr[i][0]] = cnt[val] + 1;
			}

		}


	}

}

int main() {
	cin >> n;
	cin >> x >> y;
	cin >> m;
	for (int i = 0; i < m; i++)
		cin >> arr[i][0]>>arr[i][1];
	
	
	
	bfs();
	if (cnt[y]==0) {
		cout << -1 << endl;
		return 0;
	}

	cout << cnt[y] << endl;
	return 0;
}

아이디어자체를 생각하는게 어려운 문제였습니다. 구현난이도는 굉장히 낮구요.

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

bfs 문제입니다. 

처음에 문제를 접했을때 dfs로 풀어야지 하고 신나게 작성하다가 깨닭았네요...

dfs에서는 탐색횟수 문제 때문에 visit여부를 판단해야 하는데 그렇게 되면 대다수의 상황에서 탐색이 이뤄지지 않습니다.

1)  큐에 시작좌표를 넣어주고

2)  큐의 시작점과 끝점이 같아질때 까지 반복합니다.

3)  나이트가 갈 수 있는 8가지의 경우에 수를 탐색하며 큐에 넣습니다.

4)  탐색중 도착좌표에 도착하면 arr값을 반환하며 종료합니다.

우선 arr는 자신이 몇번째에 도착했는지 카운팅하는 배열입니다. 

이때 if (arr[y + dir_y[i]][x + dir_x[i]]) continue; 이 예외처리가 필요합니다.

그 이유는 기존에 탐색했던 곳이라면 더 빠른경로가 저장되어 있을텐데 그값을 덮는 것은 더 느린 방법으로 해당좌표에 도달하는 값을 저장하는 일이기 때문입니다.

정답코드입니다. 읽어보고 꼭 직접작성해보세요. :) 화이팅

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

int t = 0, l = 0;
int start_y, start_x, defi_y, defi_x, result;
int que[90000][2] = { 0 };
int started = 0, ended = 0;
int arr[301][301] = { 0 };
int dir_y[8] = { -2,-1, 1, 2, 2, 1,-1,-2 };
int dir_x[8] = {  1, 2, 2, 1,-1,-2,-2,-1 };

int bfs() {
	int cnt = 0;

	que[ended][0] = start_y;
	que[ended][1] = start_x;
	ended++;

	while (started != ended) {
		//cout << ended << endl;
		int y = que[started ][0];
		int x = que[started ][1];
		started++;
		if (y == defi_y && x == defi_x) {
			cout << arr[y][x] << endl;
			return 0;
		}
		
		for (int i = 0; i < 8; i++) {
			if (arr[y + dir_y[i]][x + dir_x[i]]) continue;
			if ((y + dir_y[i]) >= 0 && (y + dir_y[i]) < l && (x + dir_x[i]) >= 0 && (x + dir_x[i]) < l) {
				que[ended][0] = y + dir_y[i];
				que[ended][1] = x + dir_x[i];
				ended++;
				arr[y + dir_y[i]][x + dir_x[i]] = arr[y][x] + 1;
			}
		}
	}

}

int main() {
	cin >> t;

	while (t--) {
		started = 0;
		ended = 0;
		cin >> l;

		cin >> start_y >> start_x;
		cin >> defi_y >> defi_x;

		memset(arr, 0, sizeof(arr));
		
		bfs();
	}

}

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

기본적인 dfs, bfs 문제였습니다.

숫자범위도 n=100까지이고 dfs를 사용해도 지장이 없을 것 같아 직관적인 dfs 알고리즘을 사용해 구현하였습니다.

반복문을 통해 arr[i][j]=1일땐 dfs를 호출해 해당줄에서 방문이 가능한 도시를 체크합니다.

방문 이후에는 통합시켜주며 마무리합니다.

#include <iostream>
using namespace std;
int n = 0;
int arr[101][101] = { 0 };
bool visited[101];

void dfs(int y, int x) {
	
	for (int i = 1; i <= n; i++) {
		if (arr[x][i] == 1 && !visited[i]) {
			visited[i] = 1;
			dfs(y, i);
		}	
	}
	
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) 
			cin >> arr[i][j];
			
	for (int i = 1; i <= n; i++) {

		for (int j = 1; j <= n; j++)
			visited[j] = 0;

		for (int j = 1; j <= n; j++)
			if (arr[i][j] == 1) {
				visited[j]=1;
				dfs(i, j);
			}

		for (int j = 1; j <= n; j++) {
			if (visited[j] == 1)
				arr[i][j] = 1;
		}
	}
	
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << arr[i][j] << ' ';
		}
		cout << endl;
	}
}

밑에는 dfs, bfs 를 안쓰고 O(n^3)만에 끝내는 컴팩트한 방법입니다.

#include <iostream>
using namespace std;
int main(){
	int n; 
	cin >> n;
	bool map[101][101] = {};
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++) cin >> map[i][j];
	}
	for(int k = 0; k < n; k++){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(map[i][k] && map[k][j]) map[i][j] = true;
			}
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++) cout << map[i][j] << ' ';
		cout << '\n';
	}
}

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

BFS알고리즘의 입문용 문제인 토마토 입니다. 기존 토마토와 다른점은 2차원배열을 사용한다는 점입니다.

BFS는 큐를 이용해서 문제를 해결합니다. 

입문할때 풀었던 코드라, 난잡하지만 BFS에 대해서 이해하시기는 좋을 것이라고 생각합니다. 

아래는 정답코드입니다.

#include <iostream>
#include<cstring>
#include <queue>
using namespace std;
int arr[102][102][102];
int m = 0, n = 0, cnt = 0, h = 0;
queue<int> x;
queue<int> y;
queue<int> z;

void find(void) {

	for (int k = 1; k <= h; k++)
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {

				if (arr[i][j][k] == 1) { x.push(j), y.push(i), z.push(k); }

			}
		}
}
int search(int sized) {
	if (sized == 0) return 0;
	while (sized--) {
		int x_x = x.front();
		int y_y = y.front();
		int z_z = z.front();
		if (arr[y_y - 1][x_x][z_z] == 0) y.push(y_y - 1), x.push(x_x ),z.push(z_z), arr[y_y - 1][x_x][z_z] =1;
		if (arr[y_y + 1][x_x][z_z] == 0) y.push(y_y + 1), x.push(x_x), z.push(z_z), arr[y_y + 1][x_x][z_z] = 1;
		if (arr[y_y][x_x - 1][z_z] == 0) y.push(y_y), x.push(x_x-1), z.push(z_z), arr[y_y ][x_x-1][z_z] = 1;
		if (arr[y_y][x_x + 1][z_z] == 0) y.push(y_y), x.push(x_x + 1), z.push(z_z), arr[y_y][x_x + 1][z_z] = 1;
		if (arr[y_y][x_x][z_z - 1] == 0) y.push(y_y), x.push(x_x ), z.push(z_z - 1), arr[y_y][x_x][z_z - 1] = 1;
		if (arr[y_y][x_x][z_z + 1] == 0) y.push(y_y), x.push(x_x), z.push(z_z + 1), arr[y_y][x_x][z_z + 1] = 1;
		x.pop(), y.pop(), z.pop();
	}
	return 1;
}
int search2() {
	for (int k = 1; k <= h; k++)
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				{
					if (arr[i][j][k] == 0 && arr[i - 1][j][k] == -1 && arr[i + 1][j][k] == -1 && arr[i][j - 1][k] == -1 && arr[i][j + 1][k] == -1)
						if (arr[i][j][k - 1] == -1 && arr[i][j][k + 1] == -1)
							return 1;

				}
			}
		}
	return 0;
}
int main()
{
	memset(arr, -1, sizeof(int) * 102 * 102 * 102);
	cin >> m >> n >> h;
	for (int k = 1; k <= h; k++) {
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				cin >> arr[i][j][k];
	}


	if (search2() == 1) {
		cout << -1 << '\n';
		return 0;
	}
			
		
	find();

	while (1) {
		int sd = x.size();
		if (search(sd) == 0) break;
		cnt++;
	
		
	}
		
	cout << cnt-1 << '\n';
}

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

그리디 알고리즘 문제였습니다.

우선 첫번째로 조심하셔야 하는 점은 1.도착지 2.출발지 순으로 오름차순 정렬을 해줘야 한다는 것 입니다.

저는 항상 최선의 선택을 한다는 점에 너무 집중을 해서 1.출발지 2.도착지순으로 정렬을 해서 오답을 받았습니다. ㅠㅠ

이때 

4 40

3

1 4 40

2 3 40

3 4 40

과같은 입력이 들어오면 오답처리가 됩니다. (정상출력:80 오답:40)

1) 따라서 1.도착지 2.출발지 순으로 오름차순 정렬을 해야합니다.

2) 정렬 후 m번 반복하며 해당박스들을 받을 수 있는지, 얼마나 들어갈 수 있는지 확인합니다.

( 그러기 위해서는 해당위치에 박스를 얼마나 적재했는지 표시하는 int형 배열이 필요합니다.) -> capacity

3) 1. 시작도시부터 도착도시까지 가장 많이 적재된 박스양을 구합니다.

   2. 구한 값을 통해 해당도시에서 받을 수 있는 박스량 만큼 결과 값에 더해줍니다.

   3. 시작도시부터 도착도시까지 적재한 박스양을 capacity에 더해줍니다.

3)번과 같은 과정을 m번 반복하며 결과값을 결정하는 것입니다.

정답코드입니다. 꼭 직접 작성해보세요.

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

struct info {
	int sender;
	int reciever;
	int cnt;

	
};

info arr[10000];
int capacity[10001] = { 0 };
int n = 0, c = 0, m = 0;
int result = 0;

bool cmp(info a, info b) {
	if (a.reciever < b.reciever)return true;
	else if (a.reciever == b.reciever)
		if (a.sender < b.sender)
			return true;
		
	return false;
}

int main() {
	
	cin >> n >> c;
	cin >> m;

	for (int i = 0; i < m; i++)
		cin >> arr[i].sender >> arr[i].reciever >> arr[i].cnt;

	sort(arr, arr + m,cmp); //오름차순 정렬 1.도착지 2.출발지 

	for (int i = 0; i < m; i++) { 
		
		int maxcnt = 0;
		for (int j = arr[i].sender; j < arr[i].reciever; j++)  //보내는곳부터 받는곳까지
			maxcnt = max(capacity[j], maxcnt); //capacity의 최대값을 저장합니다. 박스를 얼마나 넣을 수 있는 확인하기 위해

		int val = min(arr[i].cnt, c - maxcnt);
		result += val;
		
		for (int j = arr[i].sender; j < arr[i].reciever; j++) {
			capacity[j] += val; // 이동되면서 해당 공간만큼 할당해주어야 박스가 못 실리겠죠
		}

	}

	
	cout << result << endl;

}

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

문제만 이해하면 그리디적인 개념으로 쉽게 풀 수 있는 문제였습니다.

모든 문자열에서 인덱스값들중 가장 큰 값만을 결과문자열로 저장하고 그값과 달랐던 값을 카운트해서 결과값을 도출하면 됩니다. 

문제 조건에서 사전순으로 가장 앞서는 것을 출력한다. 라는 규칙을 주의해서 풀어 주시면 됩니다. 

아스킷 코드값을 참조하며 arr[word[j][i] - 'A']++; 의 의미가 무엇인지, 그리고 arr[26]인지 생각해보세요.

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

int n, m;
string word[1000];
int result_sum = 0;
string result;
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> word[i];
	


	for (int i = 0; i < m; i++) {
		int arr[26] = { 0 }, maxed = 0, max_index = 0;
		for (int j = 0; j < n; j++) {
			arr[word[j][i] - 'A']++; 
		}
		for (int j = 0; j < 26; j++) {
			if (maxed < arr[j]) maxed = arr[j],max_index = j;
		}
		result_sum += n - maxed;
		result += max_index + 'A';
	}

	cout << result << endl;
	cout << result_sum << endl;

}

화이팅:)

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

문제풀이 자체는 정말 쉬운데, 생각하는 과정이 필요했던 문제입니다.

N은 1 이상 1,000 이하이다. 라는 문제 조건을 가진다.

즉 모든 추들을 더하고 빼며 모든경우의 수를 도출(dfs방식)하는 방식으로는 시간 초과를 받을 수밖에 없다.

우선은 누적합 개념에 대해서 이해하셔야 합니다. 

for (int i = 0; i <= n; i++) {
		if (arr[i] > sum + 1) {
			break;
		}
		sum += arr[i];

	}

정렬되어 있는 상태라면 위와 같은 방법으로 O(n) 만에 측정할 수 없는 결과값을 도출할 수 있습니다.

sum은 0부터 시작되며 정렬되어 있는 arr배열에서 가장 작은 값부터 하나씩 증가하며 값을 확인합니다. sum + 1 보다 클 경우 sum + 1에 해당하는 값은 측정할 수 없기 때문에 break를 써서 반복문에서 나가게 되는 구조입니다. 

아래는 정답코드 입니다. 

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

int n = 0, len = 1;
int arr[1001];
int sum = 0;


int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	sort(arr, arr + n); //오름차순 정렬

	for (int i = 0; i <= n; i++) {
		if (arr[i] > sum + 1) {
			break;
		}
		sum += arr[i];

	}

	cout << sum + 1 << endl;
}

위처럼 간단한 방식으로 정답을 도출할 수 있습니다.