[풀이]백준 풀이(X/16924 등 )

문제풀이

연결 요소의 개수(16924, BFS/DFS)

연결성분(connected component)란?

  • 나누어진 각각의 그래프
  • 서로 연결되어 있는 여러 개의 고립된 부분 그래프 각각을 연결 성분이라 부른다.
  • 그룹화하는 문제랑 비슷한 것으로 보인다.

연결 성분을 찾는 방법

  • BFS, DFS 모두 이용가능하다.
  • 임의의 방문하지 않은 정점에서 BFS를 실행한다를 반복한다.

회고

  • 20분도 안걸렸다. 이제 이런 기본문제는 풀 만하니 구현력을 키워보도록 하자.

  • 인덱스를 잘 생각하자 ㅎㅎ… 자주 실수하네


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

using namespace std;
int n, m, u ,v, Answer=0;
bool visited[1001];
int check[1000][1000];


bool isInside(int y){
	if(y<n && y>=0) return true;
	else return false;
}

void bfs(int s) {
	queue<int> q;
	q.push(s);
	visited[s] = true;

	while(!q.empty()){
		int x = q.front();
		q.pop();

		for(int y=0; y<n; y++){
			//간 적 없고 인접행렬 범위 이내이면 BFS
			if(check[x][y]==1 && isInside(y)){
				visited[y] = true;
				//연결 끊어버려
				check[x][y]= check[y][x] = 0;
				q.push(y);
			}
		}
	}
}

int main() {

	cin >> n >> m;

	//init
	for(int i=0; i<1000; i++){
		visited[i] = false;
		for(int j=0; j<1000; j++){
			check[i][j] = 0;
		}
	}

	//인접행렬 제작
	for(int i=0; i<m; i++){
		cin >> u >> v;
		check[u-1][v-1] = check[v-1][u-1] = 1;
	}

	for(int i=0; i<n; i++){
		if(!visited[i]){
			bfs(i);
			Answer++;
		}
	}
	cout << Answer;
}

순열사이클(10451, BFS/DFS)

  • 1부터 N까지의 수열이 주어지고 이를 무작위로 변경한 수열이 주어진다.

  • 이 두 수열의 사이에 존재하는 순열 사이클을 찾으시오.

  • 사이클을 찾아야 하니 알고리즘이 약간 다르다.

순열사이클의 조건

  1. 2개 이상의 노드가 사이클을 이루는 것

  2. 자기 자신이 혼자 사이클 인 것

회고

  • 인접행렬이 필요없다.
  • 처음에는 사이클이 걸려있어서 복잡하게 생각했는데 엄청 간단한 문제였던 것 같다.
  • 정확한 원리는 잘 모르겠지만 ^^,, bfs를 돌면 무조건 사이클이 발생하는 것이 순열사이클 인 것 같다.
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
int test_case,n, m, Answer=0;
bool visited[1001];
int check[1000][1000];
bool isInside(int y){
	if(y<n && y>=0) return true;
	else return false;
}
void bfs(int s) {
	//조건 1. 2개 이상의 노드가 사이클을 이루는 것
	queue<int> q;
	q.push(s);
	visited[s] = true;

	while(!q.empty()){
		int x = q.front();
		q.pop();

		for(int y=0; y<n; y++){
			if(check[x][y]==1 && isInside(y))
			{
				visited[y] = true;
				check[x][y]= check[y][x] = 0;
				//이 상황에서 시간초과가 발생했던 것 같다.
				if(x==y)
				{
					break;
				}
				else
				{
					q.push(y);
				}
			}
		}
	}
	//어짜피 while이 끝났다 = 사이클을 찾았다.
}

int main() {

	cin >>test_case;
	for(int a=0; a<test_case; a++){
		cin >> n;
		//init
		for(int i=0; i<n; i++){
			visited[i] = false;
			for(int j=0; j<n; j++){
				check[i][j] = 0;
			}
		}
		//인접행렬 x
		for(int i=0; i<n; i++){
			cin >> m;
			check[i][m-1] =  1;
		}

		for(int i=0; i<n; i++){
			if(!visited[i]){
				bfs(i);
				Answer++;
			}
		}
		cout << Answer << endl;
		Answer = 0;
	}
}

[RE]리모컨(1107, 시뮬레이션)

  • 리모컨의 숫자버튼 일부가 망가진 상태
  • 리모컨은 숫자 0~9, +, - 버튼이 있다.
  • 채널은 무한대이다.(양수로만)
  • N채널로 이동하기 위한 최소 횟수는?

최소 횟수라는 말이 문제다…

생각

  • 가려는 채널 - 현재채널 값을 계산한다.
    1. 차이가 2이하면 ++ or –를 입력
    2. 그 이상이면 자릿수 차이가 적은 것을 기준으로 가장 가까운 숫자를 고른다.
  • 구현도중 시간초과로 실패처리

회고

  • 절대값처리, 자릿수로 쪼개기 등은 잘 생각한 것 같다.
  • 그러나 문제를 너무 어렵게 접근해서 못푼 것 같음.

풀이

변수

  • num_1 = 도착지와 시작위치의 차이값이다 (abs(num_1))
  • broken[12] = 부서진 버튼을 구분하는 배열이다.
  • length = check(i);

N의 범위가 50만까지이므로 모든 경우를 다 해본다. (고장난 버튼을 고려하여 100,000..?? 왜?)

for(int i=0; i<1000001; i++){
	length = check(i);
	if(length)
	{
		int k = n-i;
		if(k<0) k *= (-1);
		if(k<mini)
		{
			mini = k;
			l = length;
		}
	}
}
  1. k = 100에서 +,-버튼으로 원하는 채널까지 이동하는 경우의 수
  2. x(고장난 버튼때문에 원하는 채널에서 가장 가까운 수까지 버튼을 누른 수) + y(나머지 +,-로 이동한 수)

1/2를 비교하여 min값을 출력한다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <math.h>
#define INF 987654321

using namespace std;
int n, m, Answer=0, mini = INF, length, l;
bool broken[12];
int channel[6];

//해당 수로 이동이 가능한지를 판별
int check(int k){
	int length = 0;
	if (k==0) return broken[0] ? 0 : 1;
	//자릿수별로 계산
	while(k)
	{
		length++;
		if(broken[k%10]) return 0;
		k/=10;
	}
	return length;
}

int main() {
		cin >> n >> m;
		int num_1 = n - 100;
		if(num_1 <0) num_1 *= (-1);

		for(int i=0; i<m; i++){
			int temp;
			cin >> temp;
			//broken 0~9 숫자, 10 +, 11 -
			broken[temp] = true;
		}
		for(int i=0; i<1000001; i++){
			length = check(i);
			if(length)
			{
				int k = n-i;
				if(k<0) k *= (-1);
				if(k<mini)
				{
					mini = k;
					l = length;
				}
			}
		}
		int num_2 = mini + l;//x+y
		cout << min(num_1, num_2);
}

OX퀴즈 (EZ, 8958)

자꾸 string to char배열을 검색하게 되어서 저장용으로 적어놓는 문제

	string s;
	char ox[80];
	getline(cin, s);
	strcpy(ox,s.c_str());

역소팅

#include <functional>
sort(afterSort.begin(), afterSort.end(), greater<int>());

댓글남기기

참고