백준 12851번 숨바꼭질 2|AlgorithmBOJ|Algorithm

#12851. 숨바꼭질 2

Problem

Solution

  • 방법의 수를 구하는 것이 추가가 되었다.
  • 이는 DP를 활용하여 구한다.
  • 방문하지 않은 경로라면 방법의 수는 그대로 유지
  • 방문한 경우 + 거리 차이가 1인 경우에만 방법의 수+1
    거리 차이가 1인 경우에만 최소비용을 만족하는 경로이기 때문이다.

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <queue>
#define MAX 100000
using namespace std;
int N, K;
queue<int> q;
bool visit[MAX+1];
int dist[MAX + 1];
int cnt[MAX + 1];
void BFS() {
	q.push(N);
	visit[N] = true;
	dist[N] = 0;
	cnt[N] = 1;
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (int next : {x - 1, x + 1, x * 2}) {
			if (0 <= next && next <= MAX) {
				if (!visit[next]) {
					visit[next] = true;
					dist[next] = dist[x] + 1;
					cnt[next] = cnt[x];
					q.push(next);
				}
				else if (dist[next] == dist[x] + 1) {
					cnt[next] += cnt[x];
				}
			}
		}
		
	}
}
int main() {
	cin >> N >> K;
	BFS();
	cout << dist[K] << "\n" << cnt[K] << "\n";
	return 0;
}
백준 12100번 2048(Easy)|AlgorithmBOJ|Algorithm

#12100. 2048(Easy)

문제링크

Problem

  • N x N 크기의 보드판
  • 한 번의 이동 : 보드판에 있는 모든 블록 상하좌우 중 한 방향으로 쭉 이동
    단순히 한 칸이 아닌 해당 방향 이동할 수 있는 곳 끝까지
  • 같은 값을 가진 블록이 충돌하면 하나로 합쳐짐
    (한 번 합쳐지면 다시 합칠 수 없음 → 한 번 이동할 때 연속으로 합쳐질 수 없음 2개 → 1개인 경우만 존재)
    블록이 합쳐지면 해당 블록의 숫자를 더한 값이 된다.

Goal: 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값 구하기

  • 입력

    N: ~20
    0: 빈칸
    2^i(i= 1, 2…10): 블록 // 적어도 하나 주어짐

Solution

  • 최대 5번 이동이니 한 번 이동하면서 최대 블록 값을 갱신해주어야 한다.
    (꼭 안그래도 되겠지만)
  1. 5번 이동하는 조합을 구한다.
  2. 그 이동에 맞게 블록을 이동시킨다.
  • 해당 번째의 방향을 저장할 배열을 이용해 5개의 방향을 저장해놓고, 모두 저장했을 때 보드판을 움직이도록 한다.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    void dfs(int idx) {
    	if (idx == 5) { // 방향 5개가 저장되었을 때
    		for (int i = 0; i < n; ++i) { // 입력값인 temp를 board로 옮기고 작업을 수행한다.
    			for (int j = 0; j < n; ++j) {
    				board[i][j] = temp[i][j];
    			}
    		}
    		for (int i = 0; i < 5; ++i) { 
    			moveBlock(해당 방향);
    		}
    		return;
    	}
    	for (int i = 0; i < 4; ++i) {
    		direction[idx] = i;
    		dfs(idx+1);
    	}
    }
  • moveBlock() 블럭 이동

움직이는 방향이 좌우면 한 행의 열이 바뀌면서 board위의 블럭들이 바뀐다.
이때 좌로 이동하면 오른쪽부터 탐색, 우로 이동하면 왼쪽부터 탐색해야 한다.

움직이는 방향이 상하일 때도 위와 같은 방식이다. 이를 잘 구분해주어 update할 때 행, 열의 인덱스를 반영한다.

  • update() 아래 코드는 좌우로 이동할 때 블럭들을 갱신하는 함수다.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    void updateCol(int i, int j, queue<int> &zero) {
    	if (board[i][j] == 0) { // 0의 위치
    		zero.push(j);
    	}
    	else if (board[i][j] != 0 && board[i][j] == value) { // 블럭 값이 같을 때
    		value = 0; // 한 번에 한 번만 합치도록 0으로 초기화
    		board[i][value_idx] *= 2;
    		answer = max(answer, board[i][value_idx]);
    		board[i][j] = 0;
    		zero.push(j);
    	}
    	else if (board[i][j] != 0) {
    		value_idx = j;
    		value = board[i][j];
    		answer = max(answer, value);
    		if (!zero.empty()) {
    			zero_idx = zero.front();
    			zero.pop();
    			board[i][j] = 0;
    			board[i][zero_idx] = value;
    			zero.push(j);
    			value_idx = zero_idx; // 변경
    		}
    	}
    }
    3가지 경우를 확인하고 각 작업을 수행한다.
  1. 블럭이 없는 빈 곳: queue에 해당 위치를 넣어준다. (블럭을 옮길 때 쓰임)
  2. 합칠 대상이 되는 블럭: 이전에 저장해놓은 블럭 값과 같으면 합칠 수 있다.
    이전에 저장해놓은 블럭의 값을 2배로 하고 합칠 대상이 되는 블럭은 0으로 바꾼뒤 이 위치를 queue에 넣어준다.
  3. 합쳐질 가능성이 있는 블럭: 이 값은 나중에 합쳐질 수 있으므로 해당 값과 위치를 저장해 놓는다.
    단, queue가 비어있지 않다면 이 블럭의 위치를 옮겨주어야 하기에 queue에서 pop한 0의 위치로 해당 블럭 값을 넣어준다.
    이렇게 되면 바뀌기 전 블럭은 0이 되고 이 위치를 다시 queue에 넣어주어야 한다.
    마지막으로 위치가 바뀐 지점을 갱신해주면 된다.

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <cstdio>
#include <queue>
#include <algorithm>
#define MAX 20
using namespace std;
int n, value, value_idx, zero_idx, answer = 2;
int board[MAX][MAX];
int temp[MAX][MAX];
int direction[5]; // 방향 조합 0:상, 1:하, 2:좌, 3:우
void updateCol(int i, int j, queue<int> &zero) {
	if (board[i][j] == 0) { // 0의 위치
		zero.push(j);
	}
	else if (board[i][j] != 0 && board[i][j] == value) { // 블럭 값이 같을 때
		value = 0; // 한 번에 한 번만 합치도록 0으로 초기화
		board[i][value_idx] *= 2;
		answer = max(answer, board[i][value_idx]);
		board[i][j] = 0;
		if (!zero.empty()) {
			zero_idx = zero.front();
			zero.pop();
			board[i][zero_idx] = value;
		}
		zero.push(j);
	}
	else if (board[i][j] != 0) {
		value_idx = j;
		value = board[i][j];
		answer = max(answer, value);
		if (!zero.empty()) {
			zero_idx = zero.front();
			zero.pop();
			board[i][j] = 0;
			board[i][zero_idx] = value;
			zero.push(j);
		}
	}
}
void updateRow(int i, int j, queue<int> &zero) {
	if (board[j][i] == 0) { // 0의 위치
		zero.push(j);
	}
	else if (board[j][i] != 0 && board[j][i] == value) { // 블럭 값이 같을 때
		value = 0; // 한 번에 한 번만 합치도록 0으로 초기화
		board[value_idx][i] *= 2;
		answer = max(answer, board[value_idx][i]);
		board[j][i] = 0;
		if (!zero.empty()) {
			zero_idx = zero.front();
			zero.pop();
			board[zero_idx][i] = value;
		}
		zero.push(j);
	}
	else if (board[j][i] != 0) {
		value_idx = j;
		value = board[j][i];
		answer = max(answer, value);
		if (!zero.empty()) {
			zero_idx = zero.front();
			zero.pop();
			board[j][i] = 0;
			board[zero_idx][i] = value;
			zero.push(j);
		}
	}
}
void moveBlock(int move) {
	for (int i = 0; i < n; ++i) {
		queue<int> zero;
		value = 0; value_idx = 0; zero_idx = 0;
		if (move % 2 == 0) {
			for (int j = 0; j < n; ++j) {
				if (move == 0) {
					updateRow(i, j, zero);
				}
				else {
					updateCol(i, j, zero);
				}
			}
		}
		else {
			for (int j = n-1; j >= 0; --j) {
				if (move == 1) {
					updateRow(i, j, zero);
				}
				else {
					updateCol(i, j, zero);
				}
			}
		}
	}
}
void dfs(int idx) {
	if (idx == 5) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				board[i][j] = temp[i][j];
			}
		}
		for (int i = 0; i < 5; ++i) {
			moveBlock(direction[i]);
		}
		return;
	}
	for (int i = 0; i < 4; ++i) {
		direction[idx] = i;
		dfs(idx+1);
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			scanf("%d", &temp[i][j]);
		}
	}
	dfs(0);
	printf("%d\n", answer);
	return 0;
}

위의 코드가 틀린 Test case

7
2 2 2 2 2 2 2
2 0 2 2 2 2 2
2 0 2 2 2 2 2
2 0 2 2 2 2 2
2 2 2 0 2 2 2 
2 2 2 2 2 2 0
2 2 2 2 2 2 0
-> 32 // output

디버깅용 코드를 보면 알겠지만 방향을 3(오른쪽)으로 했을 때 board의 블럭들을 확인해보니
실제로 잘 합쳐지지 않았던 것이다. (solution에는 정답 코드를 반영)

  • 위 코드의 빨간 줄을 없애주었다. 합쳐지면 0이 있는 곳을 찾아 넣는 작업을 하면 안되기 때문이다. 이 블럭은 합쳐졌고, 이 위치는 0으로 채우고 이 인덱스를 queue에 넣어주기만 하면 된다.
  • queue가 비어있지 않다면 해당 지점에 블럭을 놓는 작업이 있는데
    이때, value_idx = zero_idx 를 추가해주어야 해당 블럭의 바뀐 위치도 알 수 있다.
    이를 추가하지 않으면 바뀌기 전 위치가 남아있어 합쳐지지 않는다.

Debug

  • 코드 보기
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    #include <cstdio>
    #include <queue>
    #include <algorithm>
    #define MAX 20
    using namespace std;
    int n, value, value_idx, zero_idx, answer = 2;
    int board[MAX][MAX];
    int temp[MAX][MAX];
    int direction[5]; // 방향 조합 0:상, 1:하, 2:좌, 3:우
    void updateCol(int i, int j, queue<int> &zero) {
    	if (board[i][j] == 0) { // 0의 위치
    		zero.push(j);
    	}
    	else if (board[i][j] != 0 && board[i][j] == value) { // 블럭 값이 같을 때
    		value = 0; // 한 번에 한 번만 합치도록 0으로 초기화
    		board[i][value_idx] *= 2;
    		answer = max(answer, board[i][value_idx]);
    		board[i][j] = 0;
    		zero.push(j);
    	}
    	else if (board[i][j] != 0) {
    		value_idx = j;
    		value = board[i][j];
    		answer = max(answer, value);
    		if (!zero.empty()) {
    			zero_idx = zero.front();
    			zero.pop();
    			board[i][j] = 0;
    			board[i][zero_idx] = value;
    			zero.push(j);
    			value_idx = zero_idx; // 변경
    		}
    	}
    	//printf("%d-%d번재: \n", i, j);
    	//for (int i = 0; i < n; ++i) {
    	//	for (int j = 0; j < n; ++j) {
    	//		printf("%d ", board[i][j]);
    	//	}
    	//	printf("\n");
    	//}
    }
    void updateRow(int i, int j, queue<int> &zero) {
    	if (board[j][i] == 0) { // 0의 위치
    		zero.push(j);
    	}
    	else if (board[j][i] != 0 && board[j][i] == value) { // 블럭 값이 같을 때
    		value = 0; // 한 번에 한 번만 합치도록 0으로 초기화
    		board[value_idx][i] *= 2;
    		answer = max(answer, board[value_idx][i]);
    		board[j][i] = 0;
    		zero.push(j);
    	}
    	else if (board[j][i] != 0) {
    		value_idx = j;
    		value = board[j][i];
    		answer = max(answer, value);
    		if (!zero.empty()) {
    			zero_idx = zero.front();
    			zero.pop();
    			board[j][i] = 0;
    			board[zero_idx][i] = value;
    			zero.push(j);
    			value_idx = zero_idx; // 변경
    		}
    	}
    }
    void moveBlock(int move) {
    	for (int i = 0; i < n; ++i) {
    		queue<int> zero;
    		value = 0; value_idx = 0; zero_idx = 0;
    		if (move % 2 == 0) {
    			for (int j = 0; j < n; ++j) {
    				if (move == 0) {
    					updateRow(i, j, zero);
    				}
    				else {
    					updateCol(i, j, zero);
    				}
    			}
    		}
    		else {
    			for (int j = n-1; j >= 0; --j) {
    				if (move == 1) {
    					updateRow(i, j, zero);
    				}
    				else {
    					updateCol(i, j, zero);
    				}
    			}
    		}
    	}
    }
    void dfs(int idx) {
    	if (idx == 5) {
    		for (int i = 0; i < n; ++i) {
    			for (int j = 0; j < n; ++j) {
    				board[i][j] = temp[i][j];
    			}
    		}
    		for (int i = 0; i < 5; ++i) {
    			moveBlock(direction[i]);
    		}
    		return;
    	}
    	for (int i = 0; i < 4; ++i) {
    		direction[idx] = i;
    		dfs(idx+1);
    	}
    }
    int main() {
    	scanf("%d", &n);
    	for (int i = 0; i < n; ++i) {
    		for (int j = 0; j < n; ++j) {
    			scanf("%d", &temp[i][j]);
    		}
    	}
    	//dfs(0);
    	direction[0] = 3; 
    	for (int i = 0; i < n; ++i) {
    		for (int j = 0; j < n; ++j) {
    			board[i][j] = temp[i][j];
    		}
    	}
    	moveBlock(direction[0])
    	printf("\n");
    	printf("%d\n", answer);
    	return 0;
    }

    2 Try

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    #include <cstdio>
    #include <queue>
    #include <algorithm>
    #define MAX 20
    using namespace std;
    int n, value, value_idx, zero_idx, answer = 2;
    int board[MAX][MAX];
    int temp[MAX][MAX];
    int direction[5]; // 방향 조합 0:상, 1:하, 2:좌, 3:우
    void updateCol(int i, int j, queue<int> &zero) {
    	if (board[i][j] == 0) { // 0의 위치
    		zero.push(j);
    	}
    	else if (board[i][j] != 0 && board[i][j] == value) { // 블럭 값이 같을 때
    		value = 0; // 한 번에 한 번만 합치도록 0으로 초기화
    		board[i][value_idx] *= 2;
    		answer = max(answer, board[i][value_idx]);
    		board[i][j] = 0;
    		zero.push(j);
    	}
    	else if (board[i][j] != 0) {
    		value_idx = j;
    		value = board[i][j];
    		answer = max(answer, value);
    		if (!zero.empty()) {
    			zero_idx = zero.front();
    			zero.pop();
    			board[i][j] = 0;
    			board[i][zero_idx] = value;
    			zero.push(j);
    			value_idx = zero_idx; // 변경
    		}
    	}
    }
    void updateRow(int i, int j, queue<int> &zero) {
    	if (board[j][i] == 0) { // 0의 위치
    		zero.push(j);
    	}
    	else if (board[j][i] != 0 && board[j][i] == value) { // 블럭 값이 같을 때
    		value = 0; // 한 번에 한 번만 합치도록 0으로 초기화
    		board[value_idx][i] *= 2;
    		answer = max(answer, board[value_idx][i]);
    		board[j][i] = 0;
    		zero.push(j);
    	}
    	else if (board[j][i] != 0) {
    		value_idx = j;
    		value = board[j][i];
    		answer = max(answer, value);
    		if (!zero.empty()) {
    			zero_idx = zero.front();
    			zero.pop();
    			board[j][i] = 0;
    			board[zero_idx][i] = value;
    			zero.push(j);
    			value_idx = zero_idx; // 변경
    		}
    	}
    }
    void moveBlock(int move) {
    	for (int i = 0; i < n; ++i) {
    		queue<int> zero;
    		value = 0; value_idx = 0; zero_idx = 0;
    		if (move % 2 == 0) {
    			for (int j = 0; j < n; ++j) {
    				if (move == 0) {
    					updateRow(i, j, zero);
    				}
    				else {
    					updateCol(i, j, zero);
    				}
    			}
    		}
    		else {
    			for (int j = n-1; j >= 0; --j) {
    				if (move == 1) {
    					updateRow(i, j, zero);
    				}
    				else {
    					updateCol(i, j, zero);
    				}
    			}
    		}
    	}
    }
    void dfs(int idx) {
    	if (idx == 5) {
    		for (int i = 0; i < n; ++i) {
    			for (int j = 0; j < n; ++j) {
    				board[i][j] = temp[i][j];
    			}
    		}
    		for (int i = 0; i < 5; ++i) {
    			moveBlock(direction[i]);
    		}
    		return;
    	}
    	for (int i = 0; i < 4; ++i) {
    		direction[idx] = i;
    		dfs(idx+1);
    	}
    }
    int main() {
    	scanf("%d", &n);
    	for (int i = 0; i < n; ++i) {
    		for (int j = 0; j < n; ++j) {
    			scanf("%d", &temp[i][j]);
    		}
    	}
    	dfs(0);
    	printf("%d\n", answer);
    	return 0;
    }
백준 11729번 하노이 탑 이동 순서|AlgorithmBOJ|Algorithm

#11729. 하노이 탑 이동 순서

Problem

  • N개의 원판
  • 첫 번째 장대 → 세 번째 장대
  • 한 번에 한 개의 원판만 다른 탑으로 이동 가능
  • 원판 위 < 원판 아래
  • 원판 이동 순서 최소화

Solution

굳이 이를 최소화시키는 방법을 생각하기보다 컴퓨터가 알아서 최소의 방법을 계산하도록 하자. → 하노이 탑도 알고리즘이 존재

  • 먼저 하나의 원판만 있을 때를 생각해보자

보조 기둥 필요없이 바로 목표 기둥으로 이동하면 된다.

1
2
3
4
5
6
7
// recursive frame
void move(원반 개수, 시작, 보조, 목표) { }

if(원반의 개수 == 1) {
	시작->목표
	return;
}

원반의 개수가 1보다 클때는 어떻게 해야 할까?

가장 큰 원반을 제외한 모든 원반이 보조 기둥에 있어야 한다. → 이게 포인트


1
2
// 맨 아래에 있는 원반을 제외한 모든 원반을 보조 기둥으로 옮긴다.
move(원반개수-1, 시작, 목표, 보조); // 시작 -> 보조

그러면 가장 큰 원반은 이 부분이 적용된다.
1
2
3
4
if(원반의 개수 == 1) {
	시작->목표
	return;
}

가장 큰 원반이 목표 기둥으로 이동하였고, 이제 이 원반은 없는 것으로 보아도 무방하다. 나머지 원반들이 모든 기둥을 이동할 수 있기 때문이다.

그러면 이제 다시 n-1개의 원반을 가지고 위와 같은 작업을 진행한다.
이때는 원래 보조 기둥을 시작 기둥으로, 시작 기둥을 보조 기둥으로 생각해야 한다.


1
move(원반개수-1, 보조, 시작, 목표);

Recursive frame의 내용을 완성해보자.
1
2
3
4
5
6
7
8
9
void move(int count, int start, int temp, int goal) {
	if(count == 1) {
        // start -> goal
        return;
    }
    move(count-1, start, goal, temp); // start->temp
    // start -> goal
    move(count-1, temp, start, goal); // temp->goal
}

주석으로 되어 있는 부분은 실질적으로 어떤 기둥에서 어떤 기둥으로 원반이 움직였는지를 나타내는 부분이다.

좀 더 깊은 이해를 위해 원반의 개수가 3개일 때 재귀함수 호출 순서를 작성하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
move(3, 1, 2, 3)
	move(2, 1, 3, 2) // 1, 2번 원반이 2번 기둥으로 가는 과정
		move(1, 1, 2, 3) 
			1에서 3으로 이동 (1번 원반)
			1에서 2로 이동 (2번 원반)
		move(1, 3, 1, 2)
			3에서 2로 이동(1번 원반)
	1에서 3으로 이동(3번 원반)
	move(2, 2, 1, 3) // 1, 2번 원반이 3번 기둥으로 가는 과정
		move(1, 2, 3, 1)
			2에서 1로 이동(1번 원반)
			2에서 3으로 이동(2번 원반)
		move(1, 1, 2, 3)
			1에서 3으로 이동 (1번 원반)

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <vector>
using namespace std;
vector<pair<int, int>> answer;
void move(int count, int start, int temp, int goal) {
	if(count == 1) {
        answer.push_back(make_pair(start, goal));
        return;
    }
    move(count-1, start, goal, temp); // start->temp
    answer.push_back(make_pair(start, goal));
    move(count-1, temp, start, goal); // temp->goal
}

int main() {
   int n;
   cin >> n;
   move(n, 1, 2, 3);
   cout << answer.size() << "\n";
   for(auto v : answer) {
       cout << v.first << " " << v.second << "\n";
   }
   return 0;
}

이동 횟수부터 출력해야 하므로, pair를 만들어 vector에 넣어주었다.

백준 11651번 좌표 정렬하기 2|AlgorithmBOJ|Algorithm

#11651. 좌표 정렬하기 2

Problem

  • 2차원 평면 위의 점 N개
  • y좌표 증가 순으로 정렬
    • 같다면 x좌표 증가 순으로 정렬

즉, y좌표 오름차순(같다면 x좌표 오름차순)으로 정렬하는 문제이다.

Solution

  • 2차원 vector에 (y, x)를 담는다. → 정렬 때문
  • sort함수를 사용 (위 문제 조건처럼 정렬된다.)
  • 출력은 거꾸로 한다.

iostream 헤더 파일의 cin과 cout을 쓰면 시간초과 되기에 cstdio를 사용하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
vector<vector<int>> positions;
int main() {
   int n, x, y;
   scanf(" %d", &n);
   positions.resize(n);
   for(int i = 0; i < n; ++i) {
        scanf(" %d %d", &x, &y);
        positions[i].push_back(y);
        positions[i].push_back(x); 
   }
   sort(positions.begin(), positions.end());
   for(auto v : positions) {
       for(int i = v.size()-1; i >= 0; --i) {
            printf("%d ", v[i]);
       }
       printf("\n");
   }
   return 0;
}

92ms가 상당히 빠른 것은 아니기에 다른 최적의 정렬 방법이 있을지도 모른다.

백준 11650번 좌표 정렬하기|AlgorithmBOJ|Algorithm

#11650. 좌표 정렬하기

문제링크

Problem

  • 2차원 평면 (x, y)
  • x 오름차순 정렬
    • x가 같다면 y 오름차순 정렬

Solution

  • 를 pair를 사용하여 저장한다.
  • pair를 사용하여 정렬하면 위 문제의 조건대로 정렬된다.

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
	int n, x, y;
	vector<pair<int, int> > answer;
	cin >> n;
	for(int i = 0; i < n; ++i) {
		cin >> x >> y;
		answer.push_back(make_pair(x, y));
	}
	sort(answer.begin(), answer.end());
	for(auto ans : answer) {
		cout << ans.first << " " << ans.second << '\n';
	}
	return 0;
}
백준 11559번 Puyo Puyo|AlgorithmBOJ|Algorithm

#11559. Puyo Puyo

문제링크

Problem

  • 뿌요는 바닥이나 다른 뿌요가 있을 때까지 아래로 떨어짐
  • 뿌요가 놓여지고 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면
    연결된 같은 색 뿌요들이 모두 사라진다.
  • 위 과정이 반복되면 1연쇄씩 늘어난다. (터지는 그룹이 동시에 여럿이라도 1연쇄)

입력

12*6의 문자
.은 빈공간
이외 뿌요 색깔 R, G, B, P, Y
뿌요들이 전부 아래로 떨어진 뒤의 상태가 주어짐

Goal: 몇 연쇄가 되는지 출력, 안터지면 0 출력

Solution

다음과 같은 과정이 일어난다.

  1. 현재 map에서 터뜨릴 수 있는 것들 터뜨리기
  2. 아래로 떨어뜨리기
  3. 위 과정 반복하기(더이상 터뜨릴 수 없는 경우 종료)
  • 터뜨리기

BFS를 활용하여 4개 이상 연속인지 확인을 한다.

void bfs(현재 위치)
    탐색용도 queue와 지울(터뜨릴)용도 queue 선언
    현재 위치 넣어주고, check
    탐색용도 queue를 전부 비울 때까지 탐색
    탐색이 끝나면(더이상 갈 때가 없는 것)
    지울 용도의 queue 크기가 4이상이면 터뜨리기

  • bfs 탐색이 끝나면 다음과 같이 4개 연속인 것들 터뜨리기

    1
    2
    3
    4
    5
    6
    7
    8
    void changeMap(queue<pair<int, int>> &erase) {
    	while (!erase.empty()) {
    		int r = erase.front().first;
    		int c = erase.front().second;
    		erase.pop();
    		map[r][c] = '.';
    	}
    }

    이 과정이 모든 map의 각 행과 열에서 이루어지면 그때 아래로 떨어뜨린다.
    (모든 위치에서 BFS탐색이 끝난 경우)

  • 아래로 떨어뜨리기

  1. Queue를 이용하여 맨 아래에서 부터 위로 탐색을 시작하여 . 인 지점을 순서대로 넣어준다.
  2. . 이 아니라면 queue에 들어간 순서대로 위치를 교환한다.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    void update() {
    	for (int i = 0; i < 6; ++i) {
    		queue<pair<int, int>> point;
    		for (int j = 11; j >= 0; --j) {
    			if (map[j][i] == '.') point.push({ j, i });
    			else {
    				if (point.empty()) continue;
    				int x = point.front().first;
    				int y = point.front().second;
    				point.pop();
    				map[x][y] = map[j][i];
    				map[j][i] = '.';
    				point.push({ j, i });
    			}
    		}
    	}
    }

    1 Try

  • 틀린 코드
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    #include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    char map[12][6];
    bool check[12][6];
    int answer, len;
    bool flag, loop = true;
    int dx[4] = { -1, 1, 0, 0 };
    int dy[4] = { 0, 0, -1, 1 };
    bool isBound(int r, int c) {
    	if (r > -1 && c > -1 && r < 12 && c < 6) return true;
    	return false;
    }
    void update() {
    	for (int i = 0; i < 6; ++i) {
    		queue<pair<int, int>> point;
    		for (int j = 11; j >= 0; --j) {
    			if (map[j][i] == '.') point.push({ j, i });
    			else {
    				if (point.empty()) continue;
    				int x = point.front().first;
    				int y = point.front().second;
    				point.pop();
    				map[x][y] = map[j][i];
    				map[j][i] = '.';
    				point.push({ j, i });
    			}
    		}
    	}
    }
    void changeMap(queue<pair<int, int>> erase) {
    	while (!erase.empty()) {
    		int r = erase.front().first;
    		int c = erase.front().second;
    		erase.pop();
    		map[r][c] = '.';
    	}
    }
    void dfs(int r, int c, queue<pair<int, int>> erase) {
    	check[r][c] = true;
    	erase.push({ r, c });
    	bool flag = false;
    	for (int i = 0; i < 4; ++i) {
    		int x = r + dx[i];
    		int y = c + dy[i];
    		if (isBound(x, y) && !check[x][y] && map[x][y] ==  map[r][c] && map[r][c] != '.') {
    			check[x][y] = true; flag = true;
    			erase.push({ x, y });
    			len++;
    			dfs(x, y, erase);
    		}
    	}
    	if (!flag && len >= 4) {
    		loop = true;
    		changeMap(erase);
    	}
    }
    int main() {
    	for (int i = 0; i < 12; ++i) {
    		for (int j = 0; j < 6; ++j) {
    			scanf(" %c", &map[i][j]);
    		}
    	}
    	queue<pair<int, int>> erase;
    	while (loop) {
    		loop = false;
    		memset(check, 0, sizeof(check));
    		for (int i = 0; i < 12; ++i) {
    			for (int j = 0; j < 6; ++j) {
    				if (map[i][j] != '.' && !check[i][j]) {
    					len = 1;
    					dfs(i, j, erase);
    				}
    			}
    		}
    		if (loop) {
    			update();
    			answer++;
    		}
    	}
    	printf("%d\n", answer);
    	return 0;
    }
    DFS로 하니까 map에서 연속인 것들을 제대로 지우지 못 한다는 것을 깨닫고
    (실제 값 확인해보면 erase queue에 연속적으로 못 넣고 return하게 됨)

BFS를 사용하여 쉽게 풀었다..(진작에 할걸)

2 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
char map[12][6];
bool check[12][6];
bool loop = true;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
bool isBound(int r, int c) {
	if (r > -1 && c > -1 && r < 12 && c < 6) return true;
	return false;
}
void update() {
	for (int i = 0; i < 6; ++i) {
		queue<pair<int, int>> point;
		for (int j = 11; j >= 0; --j) {
			if (map[j][i] == '.') point.push({ j, i });
			else {
				if (point.empty()) continue;
				int x = point.front().first;
				int y = point.front().second;
				point.pop();
				map[x][y] = map[j][i];
				map[j][i] = '.';
				point.push({ j, i });
			}
		}
	}
}
void changeMap(queue<pair<int, int>> &erase) {
	while (!erase.empty()) {
		int r = erase.front().first;
		int c = erase.front().second;
		erase.pop();
		map[r][c] = '.';
	}
}
void bfs(int r, int c){
	queue<pair<int, int>> q, erase;
	q.push({ r, c });
	erase.push({ r, c });
	check[r][c] = true;
	while (!q.empty()) {
		int length = q.size();
		for (int i = 0; i < length; ++i) {
			r = q.front().first;
			c = q.front().second;
			q.pop();
			for (int j = 0; j < 4; ++j) {
				int x = r + dx[j];
				int y = c + dy[j];
				if (isBound(x, y) && !check[x][y] && map[x][y] == map[r][c] && map[x][y] != '.') {
					check[x][y] = true;
					q.push({ x, y });
					erase.push({ x, y });
				}	
			}
		}
	}
	if (erase.size() >= 4) {
		loop = true;
		changeMap(erase);
	}
}
int main() {
	for (int i = 0; i < 12; ++i) {
		for (int j = 0; j < 6; ++j) {
			scanf(" %c", &map[i][j]);
		}
	}
	int answer = 0;
	while (loop) {
		loop = false;
		memset(check, 0, sizeof(check));
		for (int i = 0; i < 12; ++i) {
			for (int j = 0; j < 6; ++j) {
				if (map[i][j] != '.' && !check[i][j]) {
					bfs(i, j);
				}
			}
		}
		if (loop) {
			update();
			answer++;
		}
	}
	printf("%d\n", answer);
	return 0;
}

Debug

  • 디버깅용 코드
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    #include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    char map[12][6];
    bool check[12][6];
    int answer;
    bool loop = true;
    int dx[4] = { -1, 1, 0, 0 };
    int dy[4] = { 0, 0, -1, 1 };
    bool isBound(int r, int c) {
    	if (r > -1 && c > -1 && r < 12 && c < 6) return true;
    	return false;
    }
    void update() {
    	for (int i = 0; i < 6; ++i) {
    		queue<pair<int, int>> point;
    		for (int j = 11; j >= 0; --j) {
    			if (map[j][i] == '.') point.push({ j, i });
    			else {
    				if (point.empty()) continue;
    				int x = point.front().first;
    				int y = point.front().second;
    				point.pop();
    				map[x][y] = map[j][i];
    				map[j][i] = '.';
    				point.push({ j, i });
    			}
    		}
    	}
    	/*printf("start\n");
    	for (int i = 0; i < 12; ++i) {
    		for (int j = 0; j < 6; ++j) {
    			printf("%c", map[i][j]);
    		}
    		printf("\n");
    	}*/
    }
    void changeMap(queue<pair<int, int>> &erase) {
    	//printf("erase\n");
    	while (!erase.empty()) {
    		int r = erase.front().first;
    		int c = erase.front().second;
    		//printf("%d %d\n", r, c);
    		erase.pop();
    		map[r][c] = '.';
    	}
    }
    void bfs(int r, int c){
    	queue<pair<int, int>> q, erase;
    	q.push({ r, c });
    	erase.push({ r, c });
    	check[r][c] = true;
    	while (!q.empty()) {
    		int length = q.size();
    		for (int i = 0; i < length; ++i) {
    			r = q.front().first;
    			c = q.front().second;
    			q.pop();
    			for (int j = 0; j < 4; ++j) {
    				int x = r + dx[j];
    				int y = c + dy[j];
    				if (isBound(x, y) && !check[x][y] && map[x][y] == map[r][c] && map[x][y] != '.') {
    					check[x][y] = true;
    					q.push({ x, y });
    					erase.push({ x, y });
    				}	
    			}
    		}
    	}
    	if (erase.size() >= 4) {
    		loop = true;
    		changeMap(erase);
    	}
    }
    int main() {
    	for (int i = 0; i < 12; ++i) {
    		for (int j = 0; j < 6; ++j) {
    			scanf(" %c", &map[i][j]);
    		}
    	}
    	
    	while (loop) {
    		loop = false;
    		memset(check, 0, sizeof(check));
    		for (int i = 0; i < 12; ++i) {
    			for (int j = 0; j < 6; ++j) {
    				if (map[i][j] != '.' && !check[i][j]) {
    					bfs(i, j);
    				}
    			}
    		}
    		if (loop) {
    			update();
    			answer++;
    		}
    	}
    	printf("%d\n", answer);
    	return 0;
    }
  • 디버깅용 Test case

1. output : 14

Y.....
B.....
R.R...
G.R...
YG....
YBR..Y
RR...Y
YYRBRB
YRBGBB
GBRBGR
GBRBGR
GBRBGR

2. output : 1

......
......
......
......
......
......
......
......
R.....
......
RRYYGG
RRYYGG

3. output: 2

......
..R...
..R.GG
...GG.
..R...
......
..R...
......
R.....
....G.
RRY..G
RRYYGG
백준 11047번 동전 0|AlgorithmBOJ|Algorithm

#11047. 동전 0

문제링크

Problem

  • 동전의 종류 N
  • 동전을 적절히 사용해 합을 K로 만드려고 한다.

Goal: K를 만드는데 필요한 동전 개수의 최솟값 구하기

Solution

  • 동전의 가치는 오름차순으로 주어지고
    이전 가치보다 항상 몇 배 더 크다.

    4200
    1000 4
    100     2
    6개

    4790
    4000 4 790
    500     1 290
    100 2 90
    50     1 40
    10 * 4
    12개

    12
    1, 3, 4, 5
    5 2 2
    1     2
    4개
    하지만
    4 * 3
    3개

위와 같은 상황이 일어날까?
동전의 가치가 이전 가치의 배수이기에 일어날 수 없을 것이다.

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
using namespace std;
vector<int> costs;
int main()
{
	int i, n, goal, answer = 0;
	cin >> n >> goal;
	costs.resize(n);
	for(i = 0; i < n; ++i) {
		cin >> costs[i];
	}
	while(goal != 0) {
		if(goal >= costs[i-1]) {
			goal -= costs[i-1];
			answer++;
		} else i--;
	}
	cout << answer << '\n';
	return 0;
}
백준 10989번 수 정렬하기 3|AlgorithmBOJ|Algorithm

#10989. 수 정렬하기 3

문제링크

Problem

  • 시간 제한 3초
  • 메모리 제한 8MB

Goal : 주어진 수를 오름차순으로 정렬하기

Solution

  • 메모리 제한이 8MB라는 점에 주의한다.
  • 주어진 수는 최대 천만
    수의 최댓값은 최대 만
  • int 형 배열을 천만개 크기로 만들면
    10000000 * 4 = 4천만 byte = 38…MB(이미 초과
  • 하지만 10001 크기의 배열만으로 문제를 풀 수 있다.
    40004 = 0.038..MB(충분히 통과)
  • 위의 크기만 가지고 문제를 푸려면 counting sort가 적절하다.
  • 입력으로 받은 수를 각각 세어준다. → 끝
  • ??? 진짜 끝이다. 남은건 해당 숫자만큼 차례대로 카운트한 횟수만큼 출력해주면 된다.

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
#define MAX 10000
using namespace std; // 이거 안써도 된다...
int cnt[MAX+1];
int main()
{
	int n, input;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &input);
		cnt[input]++;
	}
	for(int i = 1; i <= MAX; ++i) {
		for(int j = 0; j < cnt[i]; j++) {
			printf("%d\n", i);
		}
	}
	return 0;
}
백준 10814번 나이순 정렬|AlgorithmBOJ|Algorithm

#10814. 나이순 정렬

문제링크

Problem

  • 나이와 이름이 입력으로 주어진다.
  • 나이순으로 정렬
    • 나이가 같다면 가입한 순서로 정렬(입력 순으로)

Solution

  • 으로 key가 중복될 수 있으니 multimap을 사용한다.
  • map 자체가 key가 오름차순을 유지하도록 data를 넣어준다.
    같다면 입력순으로 된다.

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
	int n, age;
	string name;
	multimap<int, string> answer;
	cin >> n;
	for(int i = 0; i < n; ++i) {
		cin >> age >> name;
		answer.insert(make_pair(age, name));
	}
	for(auto ans : answer) {
		cout << ans.first << " " << ans.second << '\n';
	}
	return 0;
}
백준 9019번 DSLR|AlgorithmBOJ|Algorithm

#9019. DSLR

Problem

Solution

  • 이 문제는 명령어 ‘L’과 ‘R’을 어떻게 수행하느냐가 제일 중요하다.
  • 처음에 deque를 사용하여 숫자를 배열로 나누고 합치고 이러다가 시간초과…
  • 사실 사칙연산만 사용하면 위 명령어를 수행할 수 있다.
  • L 명령어

Next = (Now % 1000 * 10) + (Now / 1000)

  • R 명령어

Next = (Now / 10) + (Now % 10 * 1000)

  • 주의해야 할 사항

테스트 케이스를 여러 번 수행하는 문제이므로 초기화가 필요한 변수나 배열은 초기화를 해줘야 한다.

명령어를 저장하고 있어야 하므로, 해당 숫자를 어떻게 만들었는지 경로를 저장할 배열을, 그 숫자를 만들 때 쓴 명령어가 무엇인지 저장할 배열을 만든다.

from[a] = b a를 만들기 이전 숫자 b

how[a] = 'b' a를 만들 때 수행된 명령어 b

1 Try

  • code
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    #include <iostream>
    #include <queue>
    #include <deque>
    #include <vector>
    #include <cstring>
    #define MAX 10000
    using namespace std;
    char cmd[4] = { 'D', 'S', 'L', 'R' };
    bool check[MAX];
    int from[MAX];
    char how[MAX];
    int A, B;
    void Init() {
    	memset(check, 0, sizeof(check));
    }
    void PrintCmd(int a, int b) {
    	if (a != b) {
    		PrintCmd(a, from[b]);
    		cout << how[b];
    	}	
    }
    void BFS() {
    	queue<int> q;
    	q.push(A);
    	check[A] = true;
    	while (!q.empty()) {
    		int a = q.front();
    		q.pop();
    		if (a == B) {
    			PrintCmd(A, B);
    			cout << "\n";
    			return;
    		}
    		int d = a * 2 > MAX - 1 ? a * 2 % MAX : a * 2;
    		if (!check[d]) {
    			check[d] = true;
    			how[d] = 'D';
    			from[d] = a;
    			q.push(d);
    		}
    		int s = a == 0 ? MAX - 1 : a - 1;
    		if (!check[s]) {
    			check[s] = true;
    			how[s] = 'D';
    			from[s] = a;
    			q.push(s);
    		}
    		int cur = a;
    		deque<int> ld, rd;
    		for (int i = 0, div = 1000; i < 4; ++i, div /= 10) {
    			int num = cur / div; cur %= div;
    			ld.push_back(num); rd.push_back(num);
    		}
    		int tmp = ld.front(); ld.pop_front();
    		ld.push_back(tmp);
    		tmp = rd.back(); rd.pop_back();
    		rd.push_front(tmp);
    		int l = 0, r = 0;
    		for (int i = 0, div = 1; i < 4; ++i, div *= 10) {
    			l += ld.back() * div;
    			r += rd.back() * div;
    			ld.pop_back(); rd.pop_back();
    		}
    		if (!check[l]) {
    			check[l] = true;
    			how[l] = 'L';
    			from[l] = a;
    			q.push(l);
    		}
    		if (!check[r]) {
    			check[r] = true;
    			how[r] = 'R';
    			from[r] = a;
    			q.push(r);
    		}
    	}
    }
    int main() {
    	int T;
    	cin >> T;
    	for (int t = 0; t < T; ++t) {
    		Init();
    		cin >> A >> B;
    		BFS();
    	}
    	return 0;
    }
    시간초과

2 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <queue>
#include <cstring>
#define MAX 10000
using namespace std;
char cmd[4] = { 'D', 'S', 'L', 'R' };
bool check[MAX];
int from[MAX];
char how[MAX];
int A, B;
void Init() {
	memset(check, 0, sizeof(check));
}
void PrintCmd(int a, int b) {
	if (a != b) {
		PrintCmd(a, from[b]);
		cout << how[b];
	}	
}
void BFS() {
	queue<int> q;
	q.push(A);
	check[A] = true;
	while (!q.empty()) {
		int a = q.front();
		q.pop();
		if (a == B) {
			PrintCmd(A, B);
			cout << "\n";
			return;
		}
		int d = a * 2 % MAX;
		if (!check[d]) {
			check[d] = true;
			how[d] = 'D';
			from[d] = a;
			q.push(d);
		}
		int s = a == 0 ? MAX - 1 : a - 1;
		if (!check[s]) {
			check[s] = true;
			how[s] = 'S';
			from[s] = a;
			q.push(s);
		}
		int l = (a % 1000 * 10) + (a / 1000);
		if (!check[l]) {
			check[l] = true;
			how[l] = 'L';
			from[l] = a;
			q.push(l);
		}
		int r = (a / 10) + (a % 10 * 1000);
		if (!check[r]) {
			check[r] = true;
			how[r] = 'R';
			from[r] = a;
			q.push(r);
		}
	}
}
int main() {
	int T;
	cin >> T;
	for (int t = 0; t < T; ++t) {
		Init();
		cin >> A >> B;
		BFS();
	}
	return 0;
}