[백준] 10773번, 1260번

10773번. 제로

 

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

10773번: 제로

간단한 스택 문제이다. 그냥 스택 구조만 이해하면 바로 풀 수 있는 문제.

//num 10773

#include <iostream>
#include <stack>

using namespace std;

int main(void){
	
	int k, n;
	stack<int> s;
	int answer = 0;
	
	cin >> k;
	//cin.ignore();
	
	for(int i = 0; i<k; i++){
		cin >> n;
		//cin.ignore();
		if(n == 0){
			// 지우기
			if(!s.empty()){
				s.pop();
			} 
		}else{
			s.push(n);
		}
	}
		
	while(!s.empty()){
	
		answer += s.top();
		s.pop();
	}
	
	cout << answer << endl;
}

1260번. DFS와 BFS

단순 DFS와 BFS를 구현하면 되는 문제인데, 한 노드에서 다른 노드로 갈 때, 숫자가 작은 노드부터 traverse 한다는 점이 특이한 점이다. (이전에 알고리즘 카테고리에 있는 DFS, BFS 구현에는 이런 기능이 없다.)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<int> graph[1001];
int visited_bfs[1001];
int visited_dfs[1001];
queue<int> q;
	
void bfs(int start){
	
	q.push(start);
	visited_bfs[start] = true;
	
	while(!q.empty()){
		int x = q.front();
		cout << x << ' ';
		q.pop();
		for(int i = 0; i<graph[x].size(); i++){
			int y = graph[x][i];
			if(visited_bfs[y]!=true){
				q.push(y);
				visited_bfs[y] = true;
			}
		}
	}
}

void dfs(int x){
	
	if(visited_dfs[x] == true){
		return;
	}
	
	visited_dfs[x] = true;
	cout << x << ' ';
	for(int i = 0; i<graph[x].size(); i++){
		int y = graph[x][i];
		if(visited_dfs[y]!=true){
			dfs(y);
		}
	}
}

int main(void){
	
	int n, m, v;
	
	//get inputs
	cin >> n >> m >> v;
	
	for(int i = 0; i<m; i++){
		int start, end; 
		cin >> start >> end;
		graph[start].push_back(end);
		graph[end].push_back(start);
	}
	
	// 만약 한 노드에서 다음 노드로 넘어갈 때, 여러 초이스가 있다면
	// 작은 숫자 노드부터 가야해서, 그냥 들어온 순서대로 저장된 graph를
	// 정렬해서 작은 숫자 우선으로 traverse 할 수 있도록 sort() 이용 
	for(int i = 0; i<n; i++){
		if(graph[i].size()>0){
			sort(graph[i].begin(), graph[i].end()); 
		}
	}
	
	dfs(v);
	cout << endl;
	bfs(v);
	
}

graph에 간선의 정보가 담겨있으므로, 간선을 갖고 있는 노드의 간선 vector를 sort()해주었다. 그러면 숫자가 작은 순서대로 이웃 노드가 저장되니까, 자연스럽게 숫자 작은 노드부터 traverse하게 된다.

 

문제푸는데 Segment Fault(OutofBounds)에러가 떴다. visual studio나 dev-c++에선 일어나지 않지만 백준 사이트에 채점해보면 오류가 뜬다. 오류가 뜬 원인은 아주 단순하게도, 내가 n과 m을 잠시 헷갈려서....

 

Segment Fault는 보통 메모리 접근, 참조가 잘못 일어날 때 일어난다. 값이 없는 곳에 접근한다던가 할때...

for(int i = 0; i<m; i++){ // m이 아니라 n이어야 함!
		if(graph[i].size()>0){
			sort(graph[i].begin(), graph[i].end()); 
		}
	}

내가 코드를 처음에 이렇게 써서 틀렸는데, 간선이 n개 이니까, graph 벡터는 n개 있는 건데, 그보다 큰 숫자일 m으로 돌렸으니 자연히 에러가 난 것이다. 

 

오늘도 이렇게 바보같이 변수 구분 못하고 헤맸다 ^^...