코딩무식자 전공생

방향그래프가 주어질 때(일방 통행이므로!) 0번에서 99번노드로 가는 길이 있는지 탐색하는 문제입니다.

단순히 길이 있는지없는지만 파악하면되므로 0번노드부터 전체탐색을하여 dfs함수의 매개변수v가 99이면 99번 노드까지 탐색을

한 것이므로 그 때 길이있다고 check하여 빠져나와 출력하면됩니다. 테스트케이스가 끝날 때마다 선언 해둔 배열만 초기화해주면됩니다.

자료구조책의 dfs개념파트를 보고 충분히 풀 수 있는 문제입니다.

코드

#include<iostream>
#include<cstring>
using namespace std;
int visited[100];
int graph[100][100];
void dfs(int v);
bool check;
int main()
{
	int t, v1, v2, edge;
	for (int i = 0; i < 10; i++)
	{
		memset(visited, 0, sizeof(visited));
		memset(graph, 0, sizeof(graph));
		check = false;
		cin >> t >> edge;
		for (int i = 0; i < edge; i++)
		{
			cin >> v1 >> v2;
			graph[v1][v2] = 1;
		}
		dfs(0);
		cout << "#" << t << " ";
		if (check)
			cout << 1;
		else
			cout << 0;
		cout << endl;
	}
}
void dfs(int v)
{
	visited[v] = 1;
	//99번쨰에 도달했으므로 길이 있는것임.
	if (v == 99)
	{
		check = true;
		return;
	}
	for (int i = 0; i < 100; i++)
	{
		if (!visited[i] && graph[v][i])
			dfs(i);
	}
}

전형적인 스택 문제입니다. 이런 유형의 문제들은 자료구조책의 스택단원을 공부하면서 한번쯤은 구현해봤을 문제입니다.

코드가 길어질까봐 stl로 작성했는데 스택을 처음 공부하시는분들은 복습겸 꼭 c언어 스타일로 구현해볼것을 권장합니다.

코드

#include<iostream>
#include<stack>
#include<string>
using namespace std;
int main()
{
	for (int t = 1; t <= 10; t++)
	{
		int len;
		cin >> len;
		stack<char>s;
		bool check = true;
		for (int i = 0; i < len; i++)
		{
			char c;
			cin >> c;
			switch (c)
			{
			case '[':
			case '{':
			case '<':
			case '(':
				s.push(c);
				break;
			case ']':
			case '}':
			case ')':
			case '>':
				if (s.empty())
				{
					check = false;
					break;
				}
				char pop = s.top();
				s.pop();
				if ((pop == '(' && c != ')') || (pop == '[' && c != ']') || (pop == '{' && c != '}') || (pop == '<' && c != '>'))
				{
					check = false;
					break;
				}
			}
		}
		cout << "#" << t << " ";
		if ((!s.empty() || check == false))
			cout << 0;
		else cout << 1;
			cout << endl;




	}

}

꼭 재귀호출을 이용해서 풀어야 하는 문제입니다.

재귀함수의 사용을 어려워하시는 분들은 이런 간단한 문제부터 조금씩 풀어보는게 분명 도움이 된다고생각합니다!

integer범위를 넘지않는 선에서 입력받아서 n의 m승을 구하면됩니다.

재귀함수는 짤 때 부터 함수를 종료하는 선언문을 먼저 작성하는게 좋은 습관입니다.

코드

#include<iostream>
using namespace std;
int func(int n, int m);
int main()
{
	int n, m, t;
	for (int i = 1; i <= 10; i++)
	{
		cin >> t;
		cin >> n >> m;
		cout << "#" << i << " ";
		cout << func(n, m) << endl;
	}
}
int func(int n, int m)
{
	if (m == 0)
		return 1;
	if (m == 1)
		return n;
	return n * func(n,m - 1);
}

굳이 스택을 쓰지않아도 되는 문제입니다. 

(스택으로 푸신분들 보니 엄청 복잡한 것 같습니다...)

문자열을 굳이 문자열 통으로 입력받지않고 문자 하나씩 입력하면서 숫자가 입력될 때만 더해서 값을 출력하면됩니다.

코드

#include<iostream>
using namespace std;
int main()
{
	int n;
	char word;
	for (int i = 1; i <= 10; i++)
	{
		cin >> n;
		int sum = 0;
		for (int i = 0; i < n; i++)
		{
			cin >> word;
			if (word >= '0' && word <= '9')
				sum += word - '0';
		}
		cout << '#' << i << " ";
		cout << sum << endl;
	}
}