작은시작

www.acmicpc.net/problem/2644

BFS 코드

촌수를 찾는다는건 가장 짧은 거리를 찾는 것과 같다고 볼 수있으므로 BFS를 이용할 수있다.

if (map[abc][i] == 1 && arr[i] == 0)

arr배열을 통해 거리값들을 받으면서 지나오지않은 노드만 queue에 넣어준다.

#include<iostream>
#include <queue>
using namespace std;
int N, X, Y, M;
int map[101][101];
int arr[101];
void bfs(int start, int end) {
	queue<int> q;
	q.push(start);
	arr[start] = 1;
	
	while (!q.empty()) {
		int abc = q.front();
		q.pop();
		for (int i = 1; i <= N; i++) {//다음노드탐색
			if (map[abc][i] == 1 && arr[i] == 0) { //부모가 될수 있는가 + 이미 다녀온 노드 아닌경우 
				q.push(i);
				arr[i] = arr[abc] + 1;
			}
		}

	}
}
int main() {
	cin >> N >> X >> Y >> M;

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		map[a][b] = 1;
		map[b][a] = 1;

	}
	bfs(X, Y);

	if (arr[Y] != 0) {
		cout << arr[Y];
	}
	else cout << -1;




	return 0;
}

DFS 코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N, X, Y, M;
int map[101][101];
int visited[101];
bool flag;
int cnt;
void dfs(int p, int s,int level,int before) { //이전값 들고다니기 
	if (p == s) {
		flag = true;
		cnt = level;
		return;
	}

	for (int i = 1; i <= N; i++) {
		if (map[p][i] == 1) {
			if (i == before) continue; 	//양방향 트리이므로 cycle을 방지하기위해 before

			dfs(i, s, level + 1,p);
		}

	}

}

int main() {
	cin >> N >> X >> Y >> M;

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		map[a][b] = 1;
		map[b][a] = 1;

	}


	dfs(X,Y,0,0);
	if (cnt == 0) cout << -1;
	else cout << cnt;


	return 0;
}

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

코드 설명

연산 (-,+)을 branch로 생각하여 DFS를 구성하였다.

처음 main문에서 넘겨주는 값을 number[level]로 했다가 바닥조건에서 이를 고려안해서 실수했다....

프로그래머스 환경에서 dfs 디버깅은 좀 쉽지 않은것 같다...

코드

#include <string>
#include <vector>

using namespace std;
int arr[2]={-1,1};
int answer=0;
void dfs(int level,int now,vector<int>&numbers,int target){
    if(level==numbers.size()){
        if(now==target) answer++;
        return;
    }
    for(int i=0;i<2;i++){
        int sum=numbers[level]*arr[i];
        now+=sum;
    
        dfs(level+1,now,numbers, target);
        now-=sum;
        
    }
    
}
int solution(vector<int> numbers, int target) {
    
    
    int n=numbers.size();
    dfs(0,0,numbers,target);
    
    return answer;
}