프로그래머스 - 가장 먼 노드, 정수 삼각형

가장 먼 노드.

#include <string>
#include <vector>
#include<stack>
#include<queue>
#include<iostream>
#define N 20001

using namespace std;
bool visit[N] = { 0 };
vector<int> adj[N];
//stack<int> st;
int maxv = 0;	
vector<int> ans;
queue<int> q;
queue<int> dep;

void dfs(int cur,int depth) {
	if (depth == maxv) {
		ans.push_back(cur);
	}

	if (depth > maxv) {
		maxv = depth;
		ans.clear();
		ans.push_back(cur);
	}
	
	for (int i = 0; i < adj[cur].size(); i++) {
		if (visit[i] == 0) {
			visit[i] = 1;
			dfs(adj[cur][i],depth+1);
			visit[i] = 0;
		}
	}
}

void bfs() {
	q.push(1);
	dep.push(0);
	visit[1] = 1;

	while (!q.empty()) {
		int cur = q.front();
		int cur_dep = dep.front();
		q.pop();
		dep.pop();

		if (maxv == cur_dep) {
		//	cout << maxv << " " << cur << "\n";
			ans.push_back(cur);
		}

		if (maxv < cur_dep) {
			ans.clear();
			maxv = cur_dep;
			ans.push_back(cur);
		}

		for (int i = 0; i < adj[cur].size(); i++) {
			if (visit[adj[cur][i]] == 0) {
				visit[adj[cur][i]] = 1;
				q.push(adj[cur][i]);
				dep.push(cur_dep+1);
			}
		}
	}
}

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

	for (int i = 0; i < edge.size(); i++) {
		adj[edge[i][0]].push_back(edge[i][1]);
		adj[edge[i][1]].push_back(edge[i][0]);
	}
	//dfs(1, 0);
	bfs();

	answer = ans.size();

	return answer;
}

 

음 처음에는 가장 깊은 곳을 알아야 된다 생각해서 dfs로 깊이가 최대일때만 답에 노드를 추가하도록 했다. 하지만 문제가 dfs는 재귀 방식으로 한번 리턴후 1에서 가장 먼 노드를 선택하는게 아니더라.

 

그렇게 하려면 bfs가 맞고, depth를 저장해 놓고 가장 멀때만 갱신하면 됬다.

 

다른 분들은 어떻게 풀었나 봐야 겠다.

 

음 대체적으로 bfs로 했다. 하나 이해 못한 코드가 있긴 한데. 음 왜 큐가 두개이지.?

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector<vector<int>> graph(n);
    vector<int> isVisit(n, 0);
    int length = 1;
    int count = 0;
    int i , j;
    for(i=0;i<edge.size();i++) {
        graph[edge[i][0]-1].push_back(edge[i][1]-1);
        graph[edge[i][1]-1].push_back(edge[i][0]-1);
    }
    vector<int> from;
    vector<int> tempFrom;
    from.push_back(0);
    isVisit[0] = length;
    count++;
    while(count < n) {
        length++;
        //count++;
        while(!from.empty()) {
            int start = from.front();


            for(j=0;j<graph[start].size();j++) {
                if(isVisit[graph[start][j]] == 0 ) {
                    count++;
                    //ut << graph[start][j] << endl;
                    isVisit[graph[start][j]] = length;
                    tempFrom.push_back(graph[start][j]);
                    //from.push_back(graph[start][j]);
                }
            }
            from.erase(from.begin());
        }
        from.clear();
        for(j=0;j<tempFrom.size();j++) {
            from.push_back(tempFrom[j]);
        }
        tempFrom.clear();
    }

    for(i=0;i<isVisit.size();i++) {

        if(isVisit[i] == length)
            answer++;
    }

    return answer;
}

 

정수 삼각형

왼쪽은 c를 그대로 오른쪽은 c+1로 하면 된다.

여기서 sub problem은 한 행 위까지의 답이다.

 

optimal substructure는 한 행 위의 두 값중 큰 값을 저장하는 것이다.

 

#include <string>
#include <vector>

#define Max(A,B) A > B ? A:B

using namespace std;

//optimal substructure
int dp[501][501];

int solution(vector<vector<int>> triangle) {
	int answer = 0;

	for (int i = 0; i < triangle.size(); i++) {
		for (int j = 0; j < triangle[i].size(); j++) {
			dp[i][j] = triangle[i][j];

			if (i == 0)
				;
			else {
				//
				if (j == 0) {
					dp[i][j] += dp[i - 1][j];
				}		
				else if (j == i) {
					dp[i][j] += dp[i - 1][j - 1];
				}
				else {
					dp[i][j] += Max(dp[i - 1][j-1], dp[i - 1][j]);

				}
			}
		}
	}

	int height = triangle.size();
	int maxv = 0;
	
	for (int i = 0; i < triangle[height-1].size(); i++) {
		if (dp[height-1][i] > maxv) {
			maxv = dp[height-1][i];
		}
	}
	
	answer = maxv;

	return answer;
}

 

 

등굣길

 

 

최종 목적지에서 보면 왼쪽에서 오는 경우의 수와 위에서 오는 경우의 수를 합하면 전체 경우의 수이다.

 

왠지 이 두조건이 없는거 같아서 고민해보고 질문검색을 보니까

 

내려가거나 오른쪽으로만 갈 수 있다는 조건이 빠져있다. 아니였다면 어떤 문제였을까 도대체 ㅋㅋ

 

subproblem은 즉 왼쪽 위치까지의 최단 경로, 위쪽 위치까지의 최단 경로이다.

 

optimal substructure는 해당 위치까지의 최단경로의 수를 저장하는 것이다.

 

예제만 맞았는데 왜 그런지 모르겠다.테케는 다틀림;

#include <string>
#include <vector>
#include<iostream>


using namespace std;

int dp[101][101] = { 0 };
int arr[101][101] = { 0 };
int solution(int m, int n, vector<vector<int>> puddles) {
	int answer = 0;

	for (int i = 0; i < puddles.size(); i++) {
		arr[puddles[i][0]][puddles[i][1]] = 1;
	}
	

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (i == 0 || j == 0) {
				dp[i][j] = 1;
			}
			else if(arr[i][j]!= 1) {
				int top=0, left=0;
				if (arr[i - 1][j] != 1)
					top = dp[i - 1][j];
				if (arr[i][j - 1] != 1)
					left = dp[i][j - 1];
				dp[i][j] = top + left;

				//cout << top <<" "<< left << "\n";
				
			}
			//cout << dp[i][j] << " " << i << " " << j << " " << "\n";
		}
	}

	answer = dp[n - 1][m - 1];
	return answer;
}