1. 연결 요소의 노드의 쌍은 경로로 서로 연결 되어 있다. (노드 A에서 노드 B로 가는 길이 존재한다.)
2. 각각의 연결요소에서 다른 연결 요소로 가는 경로는 없다.(노란색 집합에서 녹색 집합으로 연결된 경로가 없다.)
구하는 방법은 의외로 간단한데, DFS나 BFS를 진행하며 더이상 탐색을 할 수 없을 경우 하나의 연결 요소를 찾게 됩니다.
모든 정점에 대해서 DFS 혹은 BFS를 진행하게 된다면 모든 연결요소를 찾을 수 있게 됩니다.
1. 소스코드
#include<iostream>
using namespace std;
int matrix[1001][1001] = { 0, };
int visit[1001] = { 0, };
int n, m;
int cnt = 0;
int dfs(int cur) {
if (visit[cur] == 1) return 0;
else visit[cur] = 1;
for (int i = 1; i <= n; i++) {
//연결되었다면
if (matrix[cur][i] == 1 && visit[i] != 1) {
dfs(i);
}
}
return 1;
}
int main(void) {
cin >> n >> m;
int a, b;
for (int i = 0; i < m; i++) {
cin >> a >> b;
matrix[a][b] = 1;
matrix[b][a] = 1;
}
for (int i = 1; i <= n; i++) {
if(dfs(i)) cnt++;
}
cout << cnt << "\n";
return 0;
}
저와 같이 코드를 봤어도 이해가 안갔던 분들을 위하여 상세하게 풀이 과정을 서술해보겠습니다.
1. 풀이과정
문제에서 제시하는 바는 위와 같습니다.
1번 기둥에 있는 원판을 모두 3번으로 이동 시키는 것입니다.
하노이의 탑 문제의 규칙은 모두 알고 있다고 가정을 하겠습니다.
1-1. 이동할 방향 선정?
(아래는 도출 과정입니다. 답을 원하시는 분은 1-2로 바로 넘어가 주세요.)
제가 맨처음 접근한 방식은 다음과 같습니다.
맨위의 녀석을 2번과 3번 둘중 하나에 선택하여 이동하고 그다음 원판을 같이 이동, 이동,.. 하여 맨 밑에까지,
맨위의 작은 원판부터 접근을 했습니다.
그러자 하나의 문제점에 도달했습니다.
원판의 갯수에 따라 제일 작은 원판이 2번에 가야 할 수도, 3번에 가야 할 수도 있는 상황이 되었습니다.
조건이 많아지는 것은 매우 귀찮아지는 일입니다.
또한 알고리즘은 똑같은 동작 원리에 의하여 이동하는 것이 일반적으로 편하겠죠.
그렇다면 어떻게 해야할까요?
여기서 떠올린 점이 다음과 같습니다.
1-2. 맨 아래서 부터 선택하여 올라가자.
가장 큰 원판을 3번으로 이동시켜 놓는다면 모든 일이 해결됩니다.
가장 큰 선반을 3번으로 옮긴다고 가정했을 때, 위의 나머지 4개를 옆으로 치워줘야 3번으로 이동 할 수 있겠죠.
그렇다면 파란색 구간을 옮기기 위해서는 파란색 구간의 가장 넓은 원판을 치워야합니다.
이제 감이 좀 오시는가요?
파란색 구간을 치우기 위해서는 녹색 구간을 치워야하고..
녹색 구간을 치우기 위해서는 노란색 구간을 치워야하고..
여기서 재귀적 특징이 나타납니다.
그럼 치우는 것 까지는 알겠습니다.
그렇다면 어디로 치워줘야 할까요?
위의 그림을 살펴보면 알 수 있습니다.
편의상 가장 큰 원판을 5부터 가장 작은 원판을 1이라 하겠습니다.
먼저 우리의 목표는 1번에 있는 5번 원판을 3번으로 이동시키는 것입니다.(빨간색 화살표)
그렇게 하기 위해서는 1~4번까지의 윗부분이 자리를 비켜줘야 합니다.
파란색 부분은 2번밖에 비켜줄 자리가 없는 것을 확인할 수 있습니다.
다만 4개의 원판을 한번에 움직이는 것은 불가능하죠.
재귀의 원리에 의해서 맨 꼭대기 부터 이동해줘야 합니다.
다만 빨간색이 3번으로 가야하기 때문에 빨간색을 3번으로 먼저 보내고,
4-3-2-1 순서로 2번과 3번을 교차해서 보내주면 위와 같이 됩니다.
즉, 우리가 처음 할 일은 먼저 각 원판이 어디로 자리를 비켜줄지를 먼저 정하는겁니다.
먼저 위와 같이 1번에 있는 4개의 원판이 자리를 비켜줬다고 생각해봅시다.
그러면 가장큰 5번 원반을 3번으로 이동하기만 하면 되겠죠.
그 다음 상황은 다음과 같습니다.
5번 원판은 3번으로 이동했습니다.
그럼 나머지 원판을 3번으로 이동시켜 줘야겠죠.
이것 또한 위와 같이 각각 이동할 수 있는 위치를 살펴보고 빈 자리 에다 이동해줍니다.
여기서 빈자리는 어떻게 찾을것인가에 대한 논의가 필요합니다!!
1번 2번 3번 세개의 위가 있습니다.
1+2+3을 한다면 6이라는 값이 나오겠죠?
만약 지금 2 -> 3으로 갔다고 생각한다면, 1번이 비어있습니다.
이는 다음과 같은 식으로 구할 수 있습니다.
6 - (2 + 3) = 1
즉, 6에서 현재 위치와 도착 지점을 더한 값을 뺀다면 다음에는 어디로 보내야 할지 알 수 있습니다.
위의 예제로 생각한다면,
주황색은 3번으로 갔습니다. 2->3입니다.
그렇다면 다음에 가야할 위치는 6-(2+3) = 1 번째 라고 알 수 있습니다.
나머지 부분에 대해서도 동일하게 적용하면 됩니다.
그렇다면 아래와 같이 이동하게 되고 끝나겠죠.
2. 소스코드
#include<iostream>
using namespace std;
int cnt = 0;
/* ans() 함수는 hanoi() 함수에서 출력만 제거한 함수입니다. */
/* 문제에는 총 이동 횟수를 먼저 출력한 뒤 이동한 위치를 출력하도록 되어 있어 이동 횟수를 먼저 구하는 함수입니다 */
/* 내부적인 설명은 아래 hanoi() 함수에 적도록 하겠습니다. */
void ans(int s, int e, int n) {
if (n == 1) {
cnt++;
return;
}
int next = 6 - (s + e);
ans(s, next, n - 1);
cnt++;
ans(next, e, n - 1);
}
/* 시작과 끝, 현재 몇번째 원판을 빼야하는지에 대한 값을 매개변수로 받아옵니다. */
void hanoi(int s, int e, int n) {
if (n == 1) {
/* 만약 빼야하는 원판이 1, 즉 제일 작을 때는 다른걸 굳이 안옮기고 바로 옮길 수 있습니다 */
cout << s << " " << e<<"\n";
return;
}
/* 6에서 시작+끝 값을 빼줌으로써 다음 위치를 구합니다. */
int next = 6 - (s + e);
/* 현재의 가장 큰 원판을 옮기기 위하여 그 위의 것들을 이동시켜 줍니다. */
hanoi(s, next, n - 1);
/* 가장 큰 원판을 이동 시킵니다 */
cout << s << " " << e<<"\n";
/* 가장 큰 원판을 이동시키기 위하여 비켜준 친구들을 다시 가장큰 원판 위로 옮깁니다 */
hanoi(next, e, n - 1);
}
int main(void) {
int N;
cin >> N;
/* ans를 통하여 cnt 값을 구하고 출력 후 hanoi() 함수를 실행시켜 이동 경로를 출력합니다. */
ans(1, 3, N);
cout << cnt << "\n";
hanoi(1, 3, N);
}
제가 가장 어려웠던 것은
hanoi(s, next, n-1);
cout<<s<<" '<<e"\n";
hanoi(next, e, n-1); //이부분
이었습니다.
이부분은 아래와 같이 비켜준 원판들을 가장 큰 원판이 이동한 위치로 옮겨준다고 생각하시면 됩니다.
star = 0;을 통하여 star 변수를 0으로 만들어 main함수에서 별을 다시 생성할 수 있도록 해줍니다.
또한 별의 위치로 이동하여 공백을 출력함으로 별을 지워줍니다.
2-5. 마무리
자 이제 필수 요소들을 모두 살펴봤으니 처음 봤던 소스코드를 다시 한번 살펴보도록 하겠습니다.
자잘한 것들은 주석을 달아놓을테니 확인해보세요.
#include<iostream>
#include<conio.h>
#include<WIndows.h>
// 방향키
#define UP 72
#define LEFT 75
#define RIGHT 77
#define DOWN 80
/* 아래 위치에 별과 플레이어, 점수 등을 표시하기 위하여 선언했습니다. */
#define POS 30
using namespace std;
/* 해당 좌표로 이동하는 함수입니다. */
void gotoxy(int x, int y) {
COORD pos = { x, y };
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos);
}
/* 플레이어와 별의 위치를 기억하기 위하여 선언한 변수입니다.*/
int player_x, player_y;
int object_x, object_y;
/* 점수와 게임 화면에 별이 있는지 확인하기 위한 변수입니다. */
int score = 0;
int star = 0;
/* 위에서 다루었던 별을 만드는 함수입니다. */
void make_star() {
srand(time(NULL));
object_x = rand() % 20;
object_y = rand() % 20;
gotoxy(object_x, object_y);
printf("★");
}
/* 위에서 다루었던 플레이어의 위치를 표시하는 함수입니다. */
void draw_player() {
gotoxy(player_x, player_y);
printf("＠");
}
/* 위에서 다루었던 입력에 따른 플레이어 좌표 변환 함수입니다.*/
void move(int input) {
switch (input) {
case DOWN:
player_y++;
break;
case UP:
player_y--;
break;
case LEFT:
player_x--;
break;
case RIGHT:
player_x++;
}
}
/* 위에서 다루었던 플레이어가 별을 획득했는지(별에 닿였는지) 여부를 확인하는 함수입니다. */
void check() {
if (object_x - player_x > -2 && object_x - player_x < 2 && object_y == player_y) {
score++;
star = 0; /* 별 상태를 0으로 만들어 다시 별이 생성되게끔 합니다. */
gotoxy(object_x, object_y);
printf(" ");
}
}
int main(void) {
/* 초기 플레이어 위치는 20으로 설정했으나 얼마로 설정하든 상관없습니다. */
player_x = player_y = 20;
int c;
while (1) {
/* 플레이어와 별, 점수를 나타내기 위한 출력문입니다. */
/* POS의 위치에서 차례대로 출력합니다. */
gotoxy(POS, POS);
printf("player : (%d, %d) \n", player_x, player_y);
gotoxy(POS, POS-1);
printf("star : (%d, %d) \n", object_x, object_y);
gotoxy(POS, POS-2);
printf("score : %d", score);
/* 플레이어를 그립니다. */
draw_player();
/* 별을 획득하여 별이 없을 경우 별을 그립니다. */
if (!star) {
make_star();
star = 1; // 별을 그리고 별 상태를 1로 바꿉니다.
}
if (_kbhit()) {
/* 224 키보드 방향키값 제거 */
do { c = _getch(); } while (c != 224);
/* 기존 도형을 삭제*/
gotoxy(player_x, player_y);
printf(" ");
/* 이동 처리 */
move(_getch());
}
check();
}
}
3. 실행 화면
점수도 잘 오르고 플레이어와 별의 위치 또한 잘 나타내고 있는 모습이 보입니다.
다만 아쉬운 점은 소스코드에 종료 버튼을 넣지 않아서 컨트롤+C를 통한 콘솔 종료를 해야한다는 점이네요 ㅜ
위의 사진 처럼 키보드로 입력할 경우 키보드에 해당하는 문자를 출력하고 입력값이 얼마인지 출력하도록 했습니다.
ESC키를 누르게 되면 프로그램은 종료를 합니다.
다만 재미있는 점은 아래와 같습니다.
특수한 입력에 대한 출력
먼저, 위의 출력을 먼저 살펴보겠습니다.
? 224 이후 H: 72 와 같은 패턴으로 4가지가 나옵니다.
이는 방향키에 대한 출력입니다.
방향키를 비롯한 몇몇 입력들은 1바이트로 처리되는 아스키코드와 다르게 확장 아스키 코드를 사용하기 때문에 저렇게 두번의 변환을 통하여 표현됩니다.
아래의 : 0 이후 ; : 59와 같은 패턴은 F1~F5번을 입력했을 때 나타나는 결과입니다.
이를 통하여 우리는 일반적인 키보드 입력을 처리하는 방법과 특수한 키를 처리하는 방법 두가지를 익혔습니다.
위의 사진에서 사용한 코드는 아래와 같습니다.
#include<iostream>
#include<conio.h>
using namespace std;
/* 키입력 테스트 */
int main(void) {
int key;
while (1) {
key = _getch();
cout << (char)key << ": " << key << endl;
if (key == 27) {
cout << "ESC";
break;
}
}
}
2. kbhit()을 통한 입력 확인
kbhit()은 키 입력이 있는지 없는지 확인하는 함수입니다.
getch()는 키 입력이 생길 때 까지 기다리는 반면,
kbhit()은 입력버퍼를 확인하여 당장에 있으면 true, 없으면 false를 반환하는 함수입니다.
즉, 기다림이 없습니다.
쉽게 표현하자면 getch()은 내가 무언가를 입력해야 다음으로 진행하기 때문에 턴제 게임,
kbhit()은 입력이 있으면 하고 없으면 안하는 실시간 게임과 같은 효과를 줍니다.
kbhit()이 얼마나 중요성이 이제 실감이 나실까요?
다음의 캡처를 살펴보겠습니다.
getch()
위의 코드에서 while문이 시작할 때 "while문 시작.."이라는 문자열만 출력하도록 추가했습니다.
내가 무언가 입력을 해야만 다음 단계로 처리가 이루어집니다.
여기서 kbhit()을 이용하여 코드를 수정해보겠습니다.
#include<iostream>
#include<Windows.h> // Sleep() 함수를 사용하기 위하여 추가
#include<conio.h>
using namespace std;
/* kbhit을 추가한 키입력 테스트 */
int main(void) {
int key;
while (1) {
if (_kbhit()) {
key = _getch();
cout << (char)key << ": " << key << endl;
if (key == 27) {
cout << "ESC";
break;
}
}
else {
cout << "입력대기...\n";
Sleep(100); //Sleep을 넣지 않으면 너무 빨라 확인하기 힘들다.
}
}
}
while문 아래에 if문을 추가하여 키보드 입력이 있으면 이전과 같이 입력 값을 출력하도록 하고,
만약 입력이 없다면 "입력대기..."라는 문자열을 출력하도록 만들었습니다.
실행해본다면 다음과 같이 나타납니다.
kbhit() 이 없었을 경우에는 입력을 하지 않으면 함수의 흐름 또한 멈춥니다.
kbhit()을 넣었을 때는 입력을 하지 않아도 프로그램은 다른 작업을 계속 수행하며 함수가 흘러갑니다.
