DFS와 BFS 기본 뼈대 문제

20 May 2021

Reading time ~7 minutes

백준 1260 풀이

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

bool check[1001];
vector<int> a[1001];



void dfs(int x){
    check[x] = true;
    printf("%d ", x);
    for(int i=0; i<a[x].size(); i++){
        int y = a[x][i];
        if(check[y]==false){
            dfs(y);
        }
    }
}

void bfs(int x){
    queue<int> q;
    memset(check,false,sizeof(check));
    check[x] = true;
    q.push(x);
    while(!q.empty()){
        int f = q.front();
        q.pop();
		printf("%d ", f);
        for(int i=0; i<a[f].size(); i++){
            int y = a[f][i];
            if(check[y]==false){
                check[y] = true;
                q.push(y);
            }
        }
    }

}


int main(){
    int n, m, start;
    scanf("%d %d %d", &n, &m, &start);
    for(int i=0; i<m; i++){
        int u, v;
        scanf("%d %d", &u, &v);
        a[u].push_back(v);
        a[v].push_back(u);
    }

    for(int i=1; i<=n; i++){
        sort(a[i].begin(), a[i].end());
    }

    dfs(start);
	printf("\n");
    bfs(start);
	return 0;

}

트리의 부모 찾기(백준 11725) - DFS 기본

부모 노드를 알아보는 방법

#include <iostream>
#include <vector>

using namespace std;
#define MAX 100001

int N;
int arr[MAX];
bool visited[MAX];
vector<int> v[MAX];

void dfs(int k) {
    visited[k]=true;
    for(int i=0;i<v[k].size();i++) {
        int next = v[k][i];
        if(!visited[next]) {
            arr[next]=k; // 핵심!!!
            dfs(next);
        }
    }
}

int main() {
    cin >> N;

    for(int i=0;i<N;i++) {
        int x,y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    dfs(1);

    for(int i=2;i<=N;i++) cout << arr[i] << "\n";
}

촌수계산 (백준)

#include <vector>
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;

vector<int> rel[101];
bool visit[101];

int n;
int t1, t2;
int relNum;
int res;

void dfs(int x, int y, int cnt){

    visit[x] = true;
    if(x == y){
        res = cnt; 
    }
    for(int i=0; i<rel[x].size(); i++){
        int next = rel[x][i];
        if(!visit[next]){
            dfs(next, y, cnt+1);
        }
    }
}


int main(){
    cin >> n >> t1 >> t2 >> relNum;


    for(int i=0; i<relNum; i++){
        int u, v;
        scanf("%d %d", &u, &v);
        rel[u].push_back(v);
        rel[v].push_back(u);
    }

    dfs(t1, t2, 0);
   


    printf("%d", res);

}

내가 짠 코드

int n;
int t1, t2;
int m;
vector<int> map[101];
bool visit[101];
int arr[101];
int cnt;

void dfs(int x){
    visit[x] = true;
    for(int i=0; i<map[x].size(); i++){
        int y = map[x][i];
        if(!visit[y]){
            arr[y] = arr[x] + 1;
            dfs(y);
        }
    }
}
int main(){
    cin >> n;
    cin >> t1 >> t2;
    cin >> m;

    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;
        map[a].push_back(b);
        map[b].push_back(a);
    }

    dfs(t1);

    if(arr[t2] == 0){
        printf("%d", -1);
        return 0;
    }

    cout << arr[t2] << '\n';
}

타겟넘버 - 프로그래머스

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다

-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3

#include <string>
#include <vector>

using namespace std;

int answer = 0;

void dfs(vector<int> &numbers, int &target, int sum = 0, int cnt = 0){
    if(cnt == numbers.size()){
        if(target == sum){
            answer++;
        }
        return;
    }

    dfs(numbers, target, sum + numbers[cnt], cnt + 1);
    dfs(numbers, target, sum - numbers[cnt], cnt + 1);
}
int solution(vector<int> numbers, int target) {
    
    dfs(numbers, target);
    return answer;
}

숫자판 점프(백준)

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

int map[6][6];
bool visit[1000000];
int ans;

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, 1, -1};

void dfs(int x, int y, int sum, int cnt){
    if(cnt == 6){
        if(!visit[sum]){
            visit[sum] = true;
            ans++;
            
        }
        return;
    }
    for(int i=0; i<4; i++){
        int X = x + dx[i];
        int Y = y + dy[i];
        if(X >= 0 && Y>=0 && X<5 && Y<5){
            dfs(X, Y, sum*10 + map[X][Y] ,cnt+1);
        }
        
    }    
}

int main(){
    for(int i=0; i<5; i++){
        for(int j=0; j<5; j++){
            int m;
            scanf("%d", &m);
            map[i][j] = m;
        }
    }


    for(int i=0; i<5; i++){
        for(int j=0; j<5; j++){
            dfs(i, j, map[i][j], 1);
        }
    }

    printf("%d", ans);

}

연산자 끼워넣기(백준 14888번)

#include<iostream>
using namespace std;

int MAX = -1000000000; // -10억
int MIN = 1000000000; // 10억

int Operator[4]; // 연산자
int num[11]; // 입력 순열
int N;

void DFS(int plus, int minus, int multiple, int divide, int x, int sum)
{

	if (x == N - 1)
	{
		if (sum < MIN) MIN = sum;
		if (sum > MAX) MAX = sum;
	}

	if (plus > 0) DFS(plus - 1, minus, multiple, divide, x + 1, sum + num[x + 1]);
	if (minus > 0) DFS(plus, minus - 1, multiple, divide, x + 1, sum - num[x + 1]);
	if (multiple > 0) DFS(plus, minus, multiple - 1, divide, x + 1, sum * num[x + 1]);
	if (divide > 0) DFS(plus, minus, multiple, divide - 1, x + 1, sum / num[x + 1]);
}

int main()
{
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> num[i];
	}

	for (int i = 0; i < 4; i++)
	{
		cin >> Operator[i];
	}

	DFS(Operator[0], Operator[1], Operator[2], Operator[3], 0, num[0]);

	cout << MAX << "\n" << MIN;
}

최단거리 구하기 (BFS)

미로 탐색(백준)

문자열을 2차원배열에 집어넣을 때, 문자열을 vector로 받아서 입력 하지 않기
최단거리 구할 때 아이디어 : check[nx][ny] = check[x][y] + 1;

#include <vector>
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;

int n, m;
char map[101][101];
bool visit[101][101];
int check[101][101];
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

queue<pair<int, int>> q;

vector<string> s;

void bfs(int x, int y){
    visit[x][y] = true;    
    q.push(make_pair(x, y));
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();


        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0 <= nx  && 0<= ny && nx < n && ny < m){
                if(!visit[nx][ny] && map[nx][ny] == '1'){
                    check[nx][ny] = check[x][y] + 1;
                    visit[nx][ny] = true;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }
}

int main(){
    scanf("%d %d", &n, &m);

	for (int i = 0; i < n; i++)
	{
		scanf("%s", map[i]);
	}

    bfs(0, 0);

    printf("%d", check[n-1][m-1] + 1);
}

숨바꼭질 2

중복방문을 허용하여 탐색하는 문제
- 최단거리와 최단거리를 갖는 경우의 수를 구하는 문제
예제의 테스트케이스는 n이 5, k가 17이며, 최단경로는 4이며 4의 거리를 갖는 경로는 두가지로 다음과 같음
- 5 → 10 → 9 → 18 → 17
- 5 → 4 → 8 → 16 → 17
다른 노드들은 중복 처리를 해도 상관없지만 위에서 보듯이 17 은 몇번이고 탐색이 가능해야 한다
- 따라서 visited 배열을 통해 방문처리를 하는 위치를 변경해야 함
기존에는 다음 노드를 확인하면서 큐에 넣을 때 방문처리를 해줬음

// 앞으로 한칸 가는 경우
if(cur+1 <= m && !check[cur+1]){
    q.push(make_pair(cur+1,cnt+1));
    
    if(cur+1 != m) check[cur+1] = true;
}

(핵심)이 문제에서는 큐에서 꺼낸 후 방문 처리를 해줘야 함
- 즉, 똑같은 지점에 도달하는 방법이 여러개 존재할 수 있으므로 pop한 후 방문 여부를 확인해야 함
차이점
- 위의 경로를 보며 이해를 해야한다. 5에서 출발해 쭉쭉 진행 되다가 큐에는 같은 거리를 가지고 있는 18 16 이 동시에 있을 것이다
- 만약 변경 전처럼 큐에 넣을 때 방문 처리를 한다면 애초에 16 은 큐에 들어가지 못했을 것이다
- 이미 18 을 넣으며 방문처리를 완료했기 때문이다
- 하지만 방문 처리를 큐에서 뺄 때 한다면 큐에는 같은 거리를 가지고 있는 노드들이 동시에 존재할 것 이고 정답의 경우를 모두 확인 할 수 있을 것이다 !!

int cur = q.front().first;
int cnt = q.front().second;
q.pop();

if(ans1 < cnt) continue;

visited[cur] = true;

전체 소스 코드

#include <vector>
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <cstring>

using namespace std;

int s, target;
int ans1, num;
bool check[200001];

void bfs(int start, int cnt){
    queue<pair<int, int>> q;
    q.push(make_pair(start, cnt));
    check[start] = true;

    while(!q.empty()){
        int cur = q.front().first;
        int time = q.front().second;
        q.pop();
        check[cur] = true;

        if(num && cur == target && ans1 == time){ 
            num++;
        }
        
        if(!num && cur == target){ 
            num++;
            ans1 = time;
        }



        if(cur * 2 <= 100000  && !check[cur * 2]){
            q.push(make_pair(cur * 2, time + 1));
           
        }
        
        if(cur + 1 <= 100000 && !check[cur + 1]){
            q.push(make_pair(cur + 1, time + 1));
      
        }

        if(cur - 1 >=0 && !check[cur - 1]){
            q.push(make_pair(cur - 1, time + 1));
      
        }        

    }
}

int main(){
    cin >> s >> target;

    bfs(s, 0);

    cout << ans1 << '\n';
    cout << num << '\n';
}

Algorithm