작은시작

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://programmers.co.kr/learn/courses/30/lessons/43163

코드 설명

cnt 변수를 이용하여 한 글자가 다른 걸 찾는다 -> 재귀

재귀를 돌면서 target과 일치한다면 그때까지의 level을 tmp 변수에 담아둬서 가장 빠른 과정으로 도착할 경우를 찾는다.

(이때 min을 쓸거면 초기 result값을 큰 값으로 지정해둬야 한다!!! 여기서 실수해서 디버깅함...)

또한 result가 변화없이 다시 main으로 돌아왔다면 target을 한 번도 만나지 않았다는 의미 이므로 0을 반환해준다.

코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;
bool visited[51];
int tmp;
int result=999;
int cnt;
void dfs(int level, string& begin, string& target, vector<string>& words) {
    if (begin == target) {
        tmp = level;
        result = min(tmp, result);

        return;
    }




    for (int i = 0; i < words.size(); i++) {
        if (!visited[i]) {
            cnt = 0;
            for (int j = 0; j < words[i].size(); j++) {
                if (words[i][j] != begin[j]) {
                    cnt++;
                }
            }
            if (cnt == 1) {
                visited[i] = true;
                cout << words[i] << " ";
                dfs(level + 1, words[i], target, words);
                visited[i] = false;
            }
        }

    }


}
int solution(string begin, string target, vector<string> words) {
    int answer = 0;

    dfs(0, begin, target, words);



    if (result == 0) answer = 0;
    else {
        answer = result;
    }

    return answer;
}
int main() {

    solution("hit", "cog", { "hot", "dot", "dog", "lot", "log", "cog" });

    return 0;
}

https://programmers.co.kr/learn/courses/30/lessons/43162

코드 설명

visited배열을 통해 네트워크가 형성될때마다 표시해줍니다. 재귀를 사용하였고 level로 넘어갈때 그전 i 를 이용하여 네트워크 형성하는지 체크후 재귀하게됩니다. 

기본 그래프 문제이므로 기억이 안난다면 백준 기본문제를 다시 풀어보면 좋을것 같습니다 !! 

(main문에서 항상 dfs는 0 으로 시작한다는 습관 없애자!)

코드 

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

bool visited[201];

void dfs(int level,int n,vector<vector<int>> &computers){
    visited[level]=true;
    
    for(int i=0;i<n;i++){
        if(!visited[i] && computers[level][i]==1){
            
            dfs(i,n,computers);
            
        }
    }
    
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;

    for(int i=0;i<n;i++){
        if(!visited[i]) {
            answer++;
            dfs(i,n,computers);
        }
    }
    
    
    
    
    
    return answer;
}