작은시작

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

코드 설명

DFS, BFS의 기본을 위해 다시 복습하였다. 아직까지도 vector를 사용하는 것보다 2차원 배열을 사용하는 게 편한 것 같다....

하지만 vector를 사용하여 링크드리스트 형태로 구현하는 것도 연습하자!

코드

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int N, M, V;
int map[1001][1001];
bool visited[1001];

void DFS(int start) {
	
	
	
	
	for (int i = 0; i <= N; i++) {
		if (map[start][i] == 1 && !visited[i]) {
			visited[i] = true;
			cout << i << " ";
			DFS(i);

		}


	}



}
void BFS(int start) {
	queue<int> q;
	q.push(start);
	visited[start] = true;

	while (!q.empty()) {
		int start = q.front();
		cout << start << " ";
		q.pop();

		for (int i = 0; i <= N; i++) {
			if (!visited[i] && map[start][i]) {
				q.push(i);
				visited[i] = true;
			}


		}

	}

}
int main() {
	cin >> N >> M >> V;

	for (int i = 0; i < M; i++) {

		int a, b;
		cin >> a >> b;

		map[a][b] = 1;
		map[b][a] = 1;

	}
	cout << V << " ";
	visited[V] = true;
	DFS(V);
	memset(visited, false, sizeof(visited));
	cout << endl;
	
	
	BFS(V);








	return 0;
}

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

코드 설명

DP 메모리제이션 방식 + DFS을 합친 좋은 문제였던 것 같다.

어디 코테를 보면서 비슷한 걸 본 적이 있었는데 그 당시에 못 풀었어서 이문제는 복습을 계속해봐야 할 것 같다.

문제의 경우 DP맵 , 대나무 숲 맵 두 개로 나누어 서로 비교하며 문제를 풀어나가야 한다.

DP[y][x] : 그곳에서 시작하였을 때의 최대 이동 칸수 

즉, DP[y][x]에 값이 있다는 것은 굳이 들어가지 않아도 된다는 것을 의미한다. (이미 최대 경로가 들어가 있음)

이후에는 dfs(ny,nx)+1 을 통해 1씩 경로수를 늘려주며 재귀 탐색을 한다.

코드

//대나무먹고 자리옮기면 옮기려는 지역이 대나무가 더 많아야함(상하좌우)
//최댓값찾기
//전체탐색
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int N;
int map[501][501];

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };
int dp[501][501];
int dfs(int y, int x) {
	
	if (dp[y][x]) return dp[y][x]; // dp map에 값이 있다면 탐색하지 않고 리턴
	dp[y][x] = 1; // 없으면 처음 1부터 시작

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
		if (map[ny][nx] <= map[y][x]) continue;
		dp[y][x]= max(dp[y][x], dfs(ny, nx)+1);


	}

	return dp[y][x];  // 4방향 전부 작을때 기존 dp return


}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> map[y][x];

		}
	}

	int answer = 0;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			answer = max(answer, dfs(y, x));
		}
	}

	cout << answer;



	return 0;
}

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

코드 설명

큐를 2개를 이용하였다. start큐는 이동하는 경로, water 큐는 물의 경로이다.

일반 BFS while()문 내에 각각의 큐를 넣어 반복하였다.

전체 while()문 내에

1. 먼저 물 4방향씩 이동 ( 이동 후 물(*) 찍어주기)

2. 이후 고슴도치 4방향 탐색 이동 ( visited배열 사용했습니다)

3. 하루 증가

과 같이 계속해서 반복해주었습니다. 

배운점!!

매번 BFS를 이용하여 끝까지 탐색하는것만 생각했는데 큐의 사이즈를 이용 +  이중while문  활용 하여 한칸씩 이동후 검사하는 방법!

코드 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
char map[51][51];
int R, C;

bool flag;
bool visited[51][51];
beaver target;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,1,-1 };
int cnt;
queue<pair<int, int>> start;
queue<pair<int, int>> water;
void BFS() {
	

	while (!start.empty()) { // 전체 while
		cnt++; // 날짜하루증가
		int w_size = water.size();
		while (w_size--) { //물먼저이동

			int y = water.front().first;
			int x = water.front().second;
			water.pop();

			for (int i = 0; i < 4; i++) {
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny < 0 || nx < 0 || ny >= R || nx >= C) continue;
				if (map[ny][nx] == '*' || map[ny][nx] == 'X'||map[ny][nx]=='D') continue;
				map[ny][nx] = '*'; //맵에 물 표기 
				water.push({ ny,nx });

			}

		}

		//S이동
		int s_size = start.size();
		visited[start.front().first][start.front().second] = true;
		while (s_size--) {
			int y = start.front().first;
			int x = start.front().second;
			if (map[y][x] == 'D') { //도착
				cout << cnt - 1;
				flag = true;
			}
			start.pop();

			for (int i = 0; i < 4; i++) {
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny < 0 || nx < 0 || ny >= R || nx >= C) continue;
				if (map[ny][nx] == '*' ||map[ny][nx] == 'X') continue;
				if (!visited[ny][nx]) {
					visited[ny][nx] = true;
					start.push({ ny,nx });


				}
			}



		}




	}
	if (flag == false) cout << "KAKTUS"; //비버굴 만나지 못한경우 
	



}

int main() {

	cin >> R >> C;
	for (int y = 0; y < R; y++) {
		for (int x = 0; x < C; x++) {
			cin >> map[y][x];

			if (map[y][x] == 'S') {
				start.push({ y,x });

			}
			else if (map[y][x] == '*') {
				water.push({ y,x });
			}



		}
	}


	BFS();



	return 0;
}

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

코드 설명

강수량 높이를 0부터 하지 않아서 계속해서 반례를 찾아보느라 시간이 오래 걸렸다.

그 외 while안에 이중 for문을 담아서 계속해서 visited배열을 초기화시켜주면서 안전영역이 가장 많을 때를 저장했다.

N^3이지만 100^3이라 복잡도면에서 괜찮을 것이라 판단했다.

(반례)

3

1 1 1

1 1 1

1 1 1

을 했을때 답:1 이 나와야 한다.

코드

//안전한영역의 개수가 최대인경우 찾기
#include<iostream>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,1,-1 };
int map[101][101];

bool visited[101][101];
int N;
void run(int h,int y,int x) {
	queue<pair<int, int>> q;
	visited[y][x] = true;
	q.push({ y,x });

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || nx >= N || ny >= N) continue;
			if (!visited[ny][nx] && map[ny][nx] > h) {
				q.push({ ny,nx });
				visited[ny][nx] = true;


			}


		}



	}

}
int main() {
	cin >> N;
	int max = 0;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> map[y][x];
			if (map[y][x] > max) max = map[y][x];
		}
	}
	//////////

	////
	int aanswer = 0;
	int start = 0;
	while (start <= max) {
		int answer = 0;
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				if (!visited[y][x] && map[y][x]>start) {
					run(start,y, x);
					answer++;
				}

			}
		}
		if (aanswer < answer) aanswer = answer;
		start++;
		memset(visited, false,sizeof(visited));
	}
	cout << aanswer;



	return 0;
}