백준 15683번 감시|AlgorithmBOJ|Algorithm

#15683. 감시

Problem

Solution

  1. 설치된 CCTV 위치정보, 번호 얻기
  2. 설치된 CCTV 방향 정하기 (상하좌우: 0123)
    1번 cctv: 0, 1, 2, 3
    2번 cctv: (0, 1), (2, 3)
    3번 cctv: (0, 3), (1, 3), (0, 2), (1, 2)
    4번 cctv: (2, 0, 3), (0, 3, 1), (2, 1, 3), (0, 2, 1)
    5번 cctv: (0, 1, 2, 3)
    묶음을 왼쪽에서부터 0, 1, 2, 3이라고 정하고 (여기서 5번은 0만 갖게된다.)
    selected 배열에 넣어준다.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    void selectDirection(int idx, int cnt) {
    	if (cnt == cctv.size()) {
    		task(); // 방향대로 감시 시작
    		return;
    	}
    	int type = cctv[idx].type;
    	for (int i = 0; i < 4; ++i) {
    		if (type == 2) { // 2번 cctv는 최대 1 값만 가능
    			if (i == 2) break; 
    		}
    		if(type == 5) { // 5번 cctv는 최대 0만 가능
    			if (i == 1) break;
    		}
    		selected[idx] = i;
    		selectDirection(idx + 1, cnt + 1);
    		selected[idx] = -1;
    	}
    }
    1. 선택된 방향대로 감시 시작
  • 범위를 벗어나거나 벽을 만나면 감시를 중단한다. 그전까지는 정해진 방향대로 계속 check 표시를 한다.
  • check는 check되어 있지 않고 맵의 값이 0인 경우에만 진행한다.
    탐색된 곳의 개수를 구하기 위해서이다.

  • 전체 칸의 개수 - 탐색된 곳의 개수 - 벽의 개수 - cctv 개수 = 사각지대 개수

    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
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
129
130
131
132
133
134
135
136
#include <iostream>
#include <vector>
using namespace std;
int n, m, wall_cnt, ans;
int room[9][9];
int selected[9];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int type_two[2][2] = {{0, 1}, {2, 3}};
int type_three[4][2] = { {0, 3}, {1, 3}, {0, 2}, {1, 2} };
int type_four[4][3] = { {2, 0, 3}, {0, 3, 1}, {2, 1, 3}, {0, 2, 1} };
struct INFO {
	int x, y, type;
};
vector<INFO> cctv;
void init() {
	for (int i = 0; i < 9; ++i) selected[i] = -1;
	ans = 1e9; wall_cnt = 0;
}
bool isBound(int x, int y) {
	if (x > -1 && y > -1 && x < n && y < m) return true;
	return false;
}
void task() {
	bool check[9][9] = { 0, };
	int type, res = 0;
	for (int i = 0; i < cctv.size(); ++i) {
		int dir = selected[i];
		int x = cctv[i].x, y = cctv[i].y;
		int d_x, d_y;
		if (cctv[i].type == 1) {
			d_x = x + dx[dir];
			d_y = y + dy[dir];
			while (isBound(d_x, d_y) && room[d_x][d_y] != 6) {
				if (!check[d_x][d_y] && room[d_x][d_y] == 0) {
					check[d_x][d_y] = true;
					res++;
				}
				d_x += dx[dir];
				d_y += dy[dir];
			}
		}
		else if (cctv[i].type == 2) {
			for (int j = 0; j < 2; ++j) {
				d_x = x + dx[type_two[dir][j]];
				d_y = y + dy[type_two[dir][j]];
				while (isBound(d_x, d_y) && room[d_x][d_y] != 6) {
					if (!check[d_x][d_y] && room[d_x][d_y] == 0) {
						check[d_x][d_y] = true;
						res++;
					}
					d_x += dx[type_two[dir][j]];
					d_y += dy[type_two[dir][j]];
				}
			}
		}
		else if (cctv[i].type == 3) {
			for (int j = 0; j < 2; ++j) {
				d_x = x + dx[type_three[dir][j]];
				d_y = y + dy[type_three[dir][j]];
				while (isBound(d_x, d_y) && room[d_x][d_y] != 6) {
					if (!check[d_x][d_y] && room[d_x][d_y] == 0) {
						check[d_x][d_y] = true;
						res++;
					}
					d_x += dx[type_three[dir][j]];
					d_y += dy[type_three[dir][j]];
				}
			}
		}
		else if (cctv[i].type == 4) {
			for (int j = 0; j < 3; ++j) {
				d_x = x + dx[type_four[dir][j]];
				d_y = y + dy[type_four[dir][j]];
				while (isBound(d_x, d_y) && room[d_x][d_y] != 6) {
					if (!check[d_x][d_y] && room[d_x][d_y] == 0) {
						check[d_x][d_y] = true;
						res++;
					}
					d_x += dx[type_four[dir][j]];
					d_y += dy[type_four[dir][j]];
				}
			}
		}
		else if (cctv[i].type == 5) {
			for (int j = 0; j < 4; ++j) {
				d_x = x + dx[j];
				d_y = y + dy[j];
				while (isBound(d_x, d_y) && room[d_x][d_y] != 6) {
					if (!check[d_x][d_y] && room[d_x][d_y] == 0) {
						check[d_x][d_y] = true;
						res++;
					}
					d_x += dx[j];
					d_y += dy[j];
				}
			}
		}
	}
	res = (n * m) - res - wall_cnt - cctv.size();
	if (res < ans) ans = res;
}
void selectDirection(int idx, int cnt) {
	if (cnt == cctv.size()) {
		task();
		return;
	}
	int type = cctv[idx].type;
	for (int i = 0; i < 4; ++i) {
		if (type == 2) {
			if (i == 2) break;
		}
		if(type == 5) {
			if (i == 1) break;
		}
		selected[idx] = i;
		selectDirection(idx + 1, cnt + 1);
		selected[idx] = -1;
	}
}
int main() {
	cin >> n >> m;
	init();
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> room[i][j];
			if (room[i][j] >= 1 && room[i][j] <= 5) {
				cctv.push_back({ i, j, room[i][j] });
			}
			else if (room[i][j] == 6) wall_cnt++;
		}
	}
	selectDirection(0, 0);
	cout << ans << "\n";
	return 0;
}
백준 14891번 톱니바퀴|AlgorithmBOJ|Algorithm

#14891. 톱니바퀴

Problem

Solution

  • SWEA 모의 SW 역량 테스트 [특이한 자석](https://www.notion.so/doyuni/4013-e51a7fc5e88b4e2b999dba66b24f358b#ffc1b4f8b7b140a2a1f2e12a9f953f5b) 와 동일하다.

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
#include <cstdio>
#include <map>
using namespace std;
int magnatic[4][8];
map<int, int> task;
void rotate(int n, int dir) {
	if (dir == 1) { // 시계 방향
		int first_ele = magnatic[n][7];
		for (int i = 6; i >= 0; --i) {
			magnatic[n][i + 1] = magnatic[n][i];
		}
		magnatic[n][0] = first_ele;
	}
	else if (dir == -1) { // 반시계 방향
		int last_ele = magnatic[n][0];
		for (int i = 1; i < 8; ++i) {
			magnatic[n][i - 1] = magnatic[n][i];
		}
		magnatic[n][7] = last_ele;
	}
}
void checkRotate(int current_num, int prior_num, int dir) {
	int count_dir = dir > 0 ? -1 : 1;
	task.insert({ current_num, dir });
	if (current_num == 0) {
		if (prior_num != 1) {
			if (magnatic[current_num][2] != magnatic[current_num + 1][6]) {
				checkRotate(current_num + 1, current_num, count_dir);
			}
		}
	}
	else if (current_num == 1) {
		if (prior_num != 0) {
			if (magnatic[current_num - 1][2] != magnatic[current_num][6]) {
				checkRotate(current_num - 1, current_num, count_dir);
			}
		}
		if (prior_num != 2) {
			if (magnatic[current_num][2] != magnatic[current_num + 1][6]) {
				checkRotate(current_num + 1, current_num, count_dir);
			}
		}
	}
	else if (current_num == 2) {
		if (prior_num != 1) {
			if (magnatic[current_num - 1][2] != magnatic[current_num][6]) {
				checkRotate(current_num - 1, current_num, count_dir);
			}
		}
		if (prior_num != 3) {
			if (magnatic[current_num][2] != magnatic[current_num + 1][6]) {
				checkRotate(current_num + 1, current_num, count_dir);
			}
		}
	}
	else if (current_num == 3) {
		if (prior_num != 2) {
			if (magnatic[current_num - 1][2] != magnatic[current_num][6]) {
				checkRotate(current_num - 1, current_num, count_dir);
			}
		}
	}
}
int getScore() {
	int ans = 0, score = 1;
	for (int n = 0; n < 4; ++n) {
		if (magnatic[n][0] == 1) {
			ans += score;
		}
		score *= 2;
	}
	return ans;
}
int main() {
	for (int i = 0; i < 4; ++i) {
		for (int j = 0; j < 8; ++j) {
			scanf("%1d", &magnatic[i][j]);
		}
	}
	int k; scanf("%d", &k);
	for (int i = 0; i < k; ++i) {
		int number, dir; scanf("%d %d", &number, &dir);
		checkRotate(number - 1, -1, dir);
		for (auto e : task) {
			rotate(e.first, e.second);
		}
		task.clear();
	}
	printf("%d\n", getScore());
	return 0;
}
백준 14890번 경사로|AlgorithmBOJ|Algorithm

#14890. 경사로

문제링크

Problem

  • N x N 지도, 각 칸의 높이가 적힘
  • 길은 한 행 또는 한 열 → 길에 속한 모든 칸의 높이가 모두 같아야 지나갈 수 있음
  • 또는 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있음( 경사로 높이 1, 길이 L), 경사로 개수는 매우 많음

경사로 놓을 수 있는 경우

  • 낮은 칸과 높은 칸의 차이가 1인 경우
  • L개의 칸이 같은 높이로 연속되게 있어야 한다.

Solution

한 행

  1. 맨 왼쪽에서부터 오른쪽으로 탐색한다. (첫 번째 원소부터 마지막 원소 바로 이전까지)
  2. 현재 탐색한 원소와 바로 다음 원소와의 차이를 구한다.
  3. +1인 경우
    다음 원소부터 경사로 길이만큼 오른쪽으로 탐색을 시작한다.
    탐색하면서 다음 경우를 확인한다.
    범위를 벗어날 경우(n이상) or 경사로 길이만큼 같은 높이가 아닐 때 종료
    그게 아니면 경사로를 놓는다.
  4. -1인 경우
    현재 원소부터 경사로 길이만큼 왼쪽으로 탐색을 시작한다.
    탐색하면서 다음 경우를 확인한다.
    범위를 벗어날 경우(0미만) or 경사로 길이만큼 같은 높이가 아닐 때 or 경사로가 놓여있을 때 종료
    그게 아니면 경사로를 놓는다.
  5. 차이가 1 초과 -1 미만인 경우 종료
  6. 그게 아니라면 성공

왼쪽에서 오른쪽으로 탐색하기에

한 열 또한 위와 마찬가지로 구현한다.

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
    #include <cstdio>
    #include <cstring>
    using namespace std;
    int n, len, ans;
    int map[101][101];
    bool check[101][101];
    bool checkRow(int row) {
    	for (int j = 0; j < n - 1; ++j) {
    		if (map[row][j] - map[row][j + 1] == 1) {
    			for (int start = j + 1; start <= j + len; ++start) {
    				if (start >= n) return false; // 범위를 벗어나는 경우
    				if (map[row][j + 1] != map[row][start]) return false; // 칸의 높이가 같지 않을 때
    				check[row][start] = true; // 경사로 놓기
    			}
    		}
    		else if (map[row][j] - map[row][j + 1] == -1) {
    			for (int start = j; start > j - len; --start) {
    				if (start < 0) return false; // 범위를 벗어나는 경우
    				if (map[row][j] != map[row][start]) return false;
    				if (check[row][start]) return false;
    				check[row][start] = true;
    			}
    		}
    		else if (map[row][j] - map[row][j + 1] > 1 || map[row][j] - map[row][j + 1] < -1)
    			return false;
    	}
    	return true;
    }
    bool checkCol(int col) {
    	for (int i = 0; i < n - 1; ++i) {
    		if (map[i][col] - map[i + 1][col] == 1) {
    			for (int start = i + 1; start <= i + len; ++start) {
    				if (start >= n) return false;
    				if (map[i + 1][col] != map[start][col]) return false;
    				check[start][col] = true;
    			}
    		}
    		else if (map[i][col] - map[i + 1][col] == -1) {
    			for (int start = i; start > i - len; --start) {
    				if (start < 0) return false;
    				if (map[i][col] != map[start][col]) return false;
    				if (check[start][col]) return false;
    				check[start][col] = true;
    			}
    		}
    		else if (map[i][col] - map[i + 1][col] > 1 || map[i][col] - map[i + 1][col] < -1)
    			return false;
    	}
    }
    int main() {
    	scanf("%d %d", &n, &len);
    	for (int i = 0; i < n; ++i) {
    		for (int j = 0; j < n; ++j) {
    			scanf("%d", &map[i][j]);
    		}
    	}
    	for (int row = 0; row < n; ++row) {
    		if(checkRow(row)) ans++;
    	}
    	memset(check, 0, sizeof(check));
    	for (int col = 0; col < n; ++col) {
    		if (checkCol(col)) ans++;
    	}
    	printf("%d\n", ans);
    	return 0;
    }
    checkCol 함수에 return true 즉 반환값을 넣어주지 않았기에 틀렸다고 나왔다. bool 함수는 반드시 true와 false 둘 다 반환해주자.

이걸 몰라서 계속 문제만 주구장창 봤음…ㅠ

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
#include <cstdio>
#include <cstring>
using namespace std;
int n, len, ans;
int map[101][101];
bool check[101][101];
bool checkRow(int row) {
	for (int j = 0; j < n - 1; ++j) {
		if (map[row][j] - map[row][j + 1] == 1) {
			for (int start = j + 1; start <= j + len; ++start) {
				if (start >= n) return false; // 범위를 벗어나는 경우
				if (map[row][j + 1] != map[row][start]) return false; // 칸의 높이가 같지 않을 때
				check[row][start] = true; // 경사로 놓기
			}
		}
		else if (map[row][j] - map[row][j + 1] == -1) {
			for (int start = j; start > j - len; --start) {
				if (start < 0) return false;
				if (map[row][j] != map[row][start]) return false;
				if (check[row][start]) return false; // 경사로가 이미 놓여진 경우
				check[row][start] = true;
			}
		}
		else if (map[row][j] - map[row][j + 1] > 1 || map[row][j] - map[row][j + 1] < -1)
			return false;
	}
	return true;
}
bool checkCol(int col) {
	for (int i = 0; i < n - 1; ++i) {
		if (map[i][col] - map[i + 1][col] == 1) {
			for (int start = i + 1; start <= i + len; ++start) {
				if (start >= n) return false;
				if (map[i + 1][col] != map[start][col]) return false;
				check[start][col] = true;
			}
		}
		else if (map[i][col] - map[i + 1][col] == -1) {
			for (int start = i; start > i - len; --start) {
				if (start < 0) return false;
				if (map[i][col] != map[start][col]) return false;
				if (check[start][col]) return false;
				check[start][col] = true;
			}
		}
		else if (map[i][col] - map[i + 1][col] > 1 || map[i][col] - map[i + 1][col] < -1)
			return false;
	}
	return true;
}
int main() {
	scanf("%d %d", &n, &len);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			scanf("%d", &map[i][j]);
		}
	}
	for (int row = 0; row < n; ++row) {
		if (checkRow(row)) ans++;
	}
	memset(check, 0, sizeof(check));
	for (int col = 0; col < n; ++col) {
		if (checkCol(col)) ans++;
	}
	printf("%d\n", ans);
	return 0;
}
백준 14889번 스타트와 링크|AlgorithmBOJ|Algorithm

#14889. 스타트와 링크

문제링크

Problem

  • 총 N명 중 N/2명으로 두 팀을 만든다. (N은 짝수)
  • Sij + Sji = 능력치 ( i번과 j번 사람이 같은 팀에 속했을 때)

Goal: 두 팀의 능력치의 차이의 최솟값

Solution

  1. 먼저 두 팀을 나눠야 한다.
    1~N 중에 N/2를 골라 만들어야 하는데 중복X + 오름차순이어야 한다.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void selectTeam(int idx, int cnt) {
    	if (cnt == n / 2) { // 성공 조건
    		// 능력치 계산
    	}
    	if (idx > n) return; // 실패 조건
    	for (int i = idx; i <= n; ++i) {
    		if (selected[i] == 0) {
    			selected[i] = i;
    			selectTeam(i+1, cnt + 1);
    			selected[i] = 0;
    		}
    	}
    }
  • 1~20개의 번호를 담을 수 있는 selected 배열을 만든다.
  • 선택 되면 선택된 번호의 값을 갖는다. 선택되지 않으면 0값을 갖는다.
  • 중복 안되고, 오름차 순이기에 for문의 시작 조건을 위와 같이 한다.

  • N/2 만큼 선택하면 능력치를 계산한다.

    1. 능력치 계산

      링크팀: 0, 3, 5
      -> 능력치
      (0, 3) (0, 5)
      (3, 0) (3, 5)
      (5, 0) (5, 3)

그렇기에 선택된 숫자를 기준으로 나머지 선택된 숫자 하나만 고르면 된다.

1
2
3
4
5
6
i는 앞에 선택된 숫자 (i, j)
for (int j = 1; j <= n; ++j) {
		if (selected[j] == 0 && i != j) {
				team_start += ability[i-1][j-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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <cstdio>
#include <cmath>
using namespace std;
int n, ans;
int ability[21][21];
int selected[21];
void getDifference() {
	int team_start = 0;
	int team_link = 0;
	for (int i = 1; i <= n; ++i) {
		if (selected[i] == 0) { // 선택되지 않은 넘버가 다른 팀
			for (int j = 1; j <= n; ++j) {
				if (selected[j] == 0 && i != j) {
					team_start += ability[i-1][j-1];
				}
			}
		}
		else {
			for (int j = 1; j <= n; ++j) {
				if (selected[j] != 0 && i != j) {
					team_link += ability[i - 1][j - 1];
				}
			}
		}
	}
	unsigned int diff = abs(team_start - team_link);
	if (ans > diff) ans = diff;
}
void selectTeam(int idx, int cnt) {
	if (cnt == n / 2) {
		getDifference();
	}
	if (idx > n) return;
	for (int i = idx; i <= n; ++i) {
		if (selected[i] == 0) {
			selected[i] = i;
			selectTeam(i+1, cnt + 1);
			selected[i] = 0;
		}
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			scanf("%d", &ability[i][j]);
		}
	}
	ans = 1e9;
	selectTeam(1, 0);
	printf("%d\n", ans);
	return 0;
}
백준 14503번 로봇 청소기|AlgorithmBOJ|Algorithm

#14503. 로봇 청소기

문제링크

Problem

  • N x M 크기, 벽 또는 빈칸, 모든 외곽은 벽
  • 청소기는 바라보는 방향이 있음(상하좌우)
  • 작동
  1. 현재 위치 청소
  2. 현재 방향을 기준으로 왼쪽부터 탐색
    왼쪽에 청소하지 않은 공간이 있으면 그 방향으로 회전, 1칸 전진, 1번 진행
    없다면, 그 방향으로 회전 2번 진행
    상하좌우 모두 청소 되어 있거나 벽이라면, 방향 유지한 채 한 칸 후진 후 2번 진행 ( 현재 위치에서 4방향 다 청소나 벽일 때 현재 방향 유지한 채 후진)
    바로 위의 경우에서 뒤쪽이 벽이라 후진도 못 하는 경우 작동 종료

Goal: 로봇 청소기가 청소하는 칸의 개수 출력

방향: 0 → 위, 1 → 우, 2 → 아래, 3 → 왼

Solution

시뮬레이션 문제이다. 각 순서에 맞게 잘 구현하면 된다.

  1. 현재 탐색 지점의 값이 0이라면 청소하는 칸의 개수 1 증가 후 2로 표시
  2. 최대 5번 방향을 바꾸게 된다. (자신으로 돌아오는 것까지 포함)
  • 0(위쪽) → 3(왼쪽)
  • 1(오른쪽) → 0(위쪽)
  • 2(아래쪽) → 1(오른쪽)
  • 3(왼쪽) → 2(아래쪽)

위는 현재 방향에 따른 왼쪽 방향(다음 탐색 방향)이다.

현재 방향을 토대로 다음 방향을 결정하고 다음 방향에 맞는 좌표를 구한다.

  • 탐색 가능하면(값이 0이면) 현재 방향을 이 방향으로 바꾸고 좌표를 바꾸고 반복문 종료
  • 탐색 불가능하면 현재 방향만 이 방향으로 바꾼다.
  • 처음 방향과 같게 나오면(5번째일 경우) 후진이 가능한지 조사한다.
    가능하면 좌표만 바꿔주고 아니면 시뮬레이션을 종료한다.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    for (int i = 0; i < 5; ++i) {
    			int next_dir = left_dir[current_dir];
    			if (i == 4) {
    				int back_x = x + dx[back_dir[dir]];
    				int back_y = y + dy[back_dir[dir]];
    				if (map[back_x][back_y] == 1) return;
    				else {
    					x = back_x; y = back_y;
    					break;
    				}
    			}
    			int d_x = x + dx[next_dir];
    			int d_y = y + dy[next_dir];
    			if (map[d_x][d_y] == 0) {
    				dir = next_dir;
    				x = d_x; y = d_y;
    				break;
    			}
    			else {
    				current_dir = next_dir;
    			}
    }

    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
    #include <iostream>
    using namespace std;
    int n, m, ans;
    int map[51][51];
    int left_dir[4] = { 3, 0, 1, 2 };
    int back_dir[4] = { 2, 3, 0, 1 };
    int dx[4] = { -1, 0, 1, 0 };
    int dy[4] = { 0, 1, 0, -1 };
    bool isBound(int x, int y) {
    	if (x > -1 && y > -1 && x < n && y < m) return true;
    	return false;
    }
    void cleanMap(int x, int y, int dir) {
    	while (true) {
    		if (map[x][y] == 0) ans++;
    		map[x][y] = 2;
    		int current_dir = dir;
    		for (int i = 0; i < 5; ++i) {
    			int next_dir = left_dir[current_dir];
    			if (i == 4) {
    				int back_x = x + dx[back_dir[dir]];
    				int back_y = y + dy[back_dir[dir]];
    				if (map[back_x][back_y] == 1) return;
    				else {
    					x = back_x; y = back_y;
    					break;
    				}
    			}
    			int d_x = x + dx[next_dir];
    			int d_y = y + dy[next_dir];
    			if (map[d_x][d_y] == 0) {
    				dir = next_dir;
    				x = d_x; y = d_y;
    				break;
    			}
    			else {
    				current_dir = next_dir;
    			}
    		}	
    	}
    }
    int main() {
    	int start_x, start_y, dir;
    	cin >> n >> m;
    	cin >> start_x >> start_y >> dir;
    	for (int i = 0; i < n; ++i) {
    		for (int j = 0; j < m; ++j) {
    			cin >> map[i][j];
    		}
    	}
    	cleanMap(start_x, start_y, dir);
    	cout << ans << "\n";
    	return 0;
    }
백준 14502번 연구소|AlgorithmBOJ|Algorithm

#14502. 연구소

문제링크

Problem

  • N x M 크기, 빈 칸(0), 벽(1), 바이러스(2) 존재
  • 바이러스는 상하좌우 빈칸으로만 움직임
  • 벽을 꼭 3개 세워야 한다.

Goal: 벽을 3개 세운 뒤, 얻을 수 있는 안전 영역 크기의 최댓값
안전 영역은 벽 3개 세운 뒤 0의 개수

Solution

  1. 벽을 3개 세우는 경우의 수를 모두 구한다. (브루트 포스 - 재귀)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void buildWall(int idx, int cnt) {
    	if (cnt == 3) {
    		spreadVirus();
    		return;
    	}
    	if (idx == zero_point.size()) return;
    	buildWall(idx + 1, cnt);
    	wall[cnt].x = zero_point[idx].first;
    	wall[cnt].y = zero_point[idx].second;
    	buildWall(idx + 1, cnt+1);
    }

    0인 지점을 저장해놓은 벡터에서 3개를 선택하도록 한다.

    1. 원래의 map은 보존해야 하므로 새로운 배열에 복사를 해놓고 위에서 구한 경우의 수에 맞게 벽을 세운다.
      1
      2
      3
      4
      copyMap(); // 새로운 배열(tmp)에 복사
      for (int i = 0; i < 3; ++i) {
      		tmp[wall[i].x][wall[i].y] = 1;
      }
    2. 벽을 세운 새로운 map에서 바이러스가 퍼지도록 한다. (BFS) 
      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
      void spreadVirus() {
      	// 2번째 작업
      	// 아래부터 3번째 작업
      	queue<pair<int, int> > q;
      	for (int i = 0; i < total_virus; ++i) {
      		q.push({ virus[i].x, virus[i].y });
      	}
      	int minus_safe_area = 3;
      	while (!q.empty()) {
      		int len = q.size();
      		for (int i = 0; i < len; ++i) {
      			int x = q.front().first;
      			int y = q.front().second;
      			q.pop();
      			for (int dir = 0; dir < 4; ++dir) {
      				int d_x = x + dx[dir];
      				int d_y = y + dy[dir];
      				if (isBound(d_x, d_y) && tmp[d_x][d_y] == 0) {
      					q.push({ d_x, d_y });
      					tmp[d_x][d_y] = 2;
      					minus_safe_area++;
      				}
      			}
      		}
      	}
      	if (ans < safe_area - minus_safe_area) ans = safe_area - minus_safe_area;
      }
      BFS 탐색이 끝나면 queue가 비워지게 되므로, 다음 탐색을 위해 바이러스 위치를 저장해놓을 배열이 필요하다는 것에 주의한다.

안전영역 크기 = 원래 map의 0의 개수 - 벽 3개 - 모두 퍼진 바이러스 수

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
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m, ans, safe_area, total_virus;
int tmp[9][9];
vector<vector<int> > map;
vector<pair<int, int> > zero_point;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
struct INFO {
	int x, y;
}wall[3], virus[10];
bool isBound(int x, int y) {
	if (x > -1 && y > -1 && x < n && y < m) return true;
	return false;
}
void copyMap() {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			tmp[i][j] = map[i][j];
		}
	}
}
void spreadVirus() {
	copyMap();
	for (int i = 0; i < 3; ++i) {
		tmp[wall[i].x][wall[i].y] = 1;
	}
	queue<pair<int, int> > q;
	for (int i = 0; i < total_virus; ++i) {
		q.push({ virus[i].x, virus[i].y });
	}
	int minus_safe_area = 3;
	while (!q.empty()) {
		int len = q.size();
		for (int i = 0; i < len; ++i) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			for (int dir = 0; dir < 4; ++dir) {
				int d_x = x + dx[dir];
				int d_y = y + dy[dir];
				if (isBound(d_x, d_y) && tmp[d_x][d_y] == 0) {
					q.push({ d_x, d_y });
					tmp[d_x][d_y] = 2;
					minus_safe_area++;
				}
			}
		}
	}
	if (ans < safe_area - minus_safe_area) ans = safe_area - minus_safe_area;
}
void buildWall(int idx, int cnt) {
	if (cnt == 3) {
		spreadVirus();
		return;
	}
	if (idx == zero_point.size()) return;
	buildWall(idx + 1, cnt);
	wall[cnt].x = zero_point[idx].first;
	wall[cnt].y = zero_point[idx].second;
	buildWall(idx + 1, cnt+1);
}
int main() {
	cin >> n >> m;
	map.resize(n);
	for (int i = 0; i < n; ++i) {
		map[i].resize(m);
		for (int j = 0; j < m; ++j) {
			cin >> map[i][j];
			if (map[i][j] == 0) zero_point.push_back({ i, j });
			else if (map[i][j] == 2) {
				virus[total_virus].x = i;
				virus[total_virus++].y = j;
			}
		}
	}
	safe_area = zero_point.size();
	buildWall(0, 0);
	cout << ans << "\n";
	return 0;
}
백준 14499번 주사위 굴리기|AlgorithmBOJ|Algorithm

#14499. 주사위 굴리기

문제링크

Problem

  • N x M 지도 위에 주사위 하나
  • 오른쪽(동), 위쪽(북)
  • 주사위 위치는 (x, y) 모든 면에 0 적혀 있음
  • 지도에는 정수가 쓰여있고
    주사위가 이동한 칸에 쓰여 있는 수가 0이면 주사위 바닥면 수가 지도로 복사
    0이 아니면 지도위에 쓰여 있는 수가 주사위 바닥면으로 복사, 지도에 쓰여 있는 수는 0이 된다.

Goal: 주사위가 이동했을 때마다 주사위의 윗 면에 쓰여 있는 수를 출력
범위를 벗어나는 명령이면 움직이지 않고 출력도 하지 않는다.

1: 오른쪽, 2: 왼쪽, 3: 위쪽, 4: 아래쪽으로 이동한다.

Solution

  • 주사위 6면의 정보를 가지고 있어야 한다.
    1
    2
    3
    4
    5
    struct INFO {
    	int up = 0, down = 0, front = 0, back = 0, left = 0, right = 0;
    	int x, y;
    }dice;
    // 윗면, 아랫면, 앞면, 뒷면, 왼면, 오른면
  • 주사위를 움직일 때 6면의 정보가 방향에 맞게 업데이트 되어야 한다.

먼저 범위를 검사하고 검사한 후에 주사위 위치를 변경해준다.

  1. 오른쪽 이동
    위 → 오른 → 아래 → 왼 → 위
  2. 왼쪽 이동
    위 → 왼 → 아래 → 오른 → 위
  3. 위쪽 이동
    위 → 뒤 → 아래 → 앞 → 위
  4. 아래쪽 이동
    위 → 앞 → 아래 → 뒤 → 위

값을 제대로 업데이트 하기 위해서 사이클이 시작되기 전 값을 저장해놓고 순서대로 덮어씌우는 방식으로 값을 갱신한다.

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
void moveDice(int dir) {
	int d_x = dice.x + dx[dir - 1];
	int d_y = dice.y + dy[dir - 1];
	if (isBound(d_x, d_y)) {
		dice.x = d_x; dice.y = d_y;
		int tmp = 0;
		if (dir == 1) { // right
			tmp = dice.left;
			dice.left = dice.down;
			dice.down = dice.right;
			dice.right = dice.up;
			dice.up = tmp;
		}
		else if (dir == 2) { // left
			tmp = dice.right;
			dice.right = dice.down;
			dice.down = dice.left;
			dice.left = dice.up;
			dice.up = tmp;
		}
		else if (dir == 3) { // up
			tmp = dice.front;
			dice.front = dice.down;
			dice.down = dice.back;
			dice.back = dice.up;
			dice.up = tmp;
		}
		else if (dir == 4) { // down
			tmp = dice.back;
			dice.back = dice.down;
			dice.down = dice.front;
			dice.front = dice.up;
			dice.up = tmp;
		}
}

  • 움직였을 때
    • 지도의 칸이 0이면, 주사위 바닥면 수 → 지도
    • 지도의 칸이 0이 아니면, 지도 → 주사위 바닥면 수 & 0 → 지도
      1
      2
      3
      4
      5
      6
      if (map[dice.x][dice.y] == 0) map[dice.x][dice.y] = dice.down;
      else {
      		dice.down = map[dice.x][dice.y];
      		map[dice.x][dice.y] = 0;
      }
      cout << dice.up << "\n"; // 윗면 출력

      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
      #include <iostream>
      #include <vector>
      using namespace std;
      int n, m;
      vector<vector<int> > map;
      int dx[4] = { 0, 0, -1, 1 };
      int dy[4] = { 1, -1, 0, 0 };
      struct INFO {
      	int up = 0, down = 0, front = 0, back = 0, left = 0, right = 0;
      	int x, y;
      }dice;
      bool isBound(int x, int y) {
      	if (x > -1 && y > -1 && x < n && y < m) return true;
      	return false;
      }
      void moveDice(int dir) {
      	int d_x = dice.x + dx[dir-1];
      	int d_y = dice.y + dy[dir-1];
      	if (isBound(d_x, d_y)) {
      		dice.x = d_x; dice.y = d_y;
      		int tmp = 0;
      		if (dir == 1) { // right
      			tmp = dice.left;
      			dice.left = dice.down;
      			dice.down = dice.right;
      			dice.right = dice.up;
      			dice.up = tmp;
      		}
      		else if (dir == 2) { // left
      			tmp = dice.right;
      			dice.right = dice.down;
      			dice.down = dice.left;
      			dice.left = dice.up;
      			dice.up = tmp;
      		}
      		else if (dir == 3) { // up
      			tmp = dice.front;
      			dice.front = dice.down;
      			dice.down = dice.back;
      			dice.back = dice.up;
      			dice.up = tmp;
      		}
      		else if (dir == 4) { // down
      			tmp = dice.back;
      			dice.back = dice.down;
      			dice.down = dice.front;
      			dice.front = dice.up;
      			dice.up = tmp;
      		}
      		if (map[dice.x][dice.y] == 0) map[dice.x][dice.y] = dice.down;
      		else {
      			dice.down = map[dice.x][dice.y];
      			map[dice.x][dice.y] = 0;
      		}
      		cout << dice.up << "\n";
      	}
      }
      int main() {
      	int start_x, start_y, k, dir;
      	cin >> n >> m >> start_x >> start_y >> k;
      	dice.x = start_x; dice.y = start_y;
      	map.resize(n);
      	for (int i = 0; i < n; ++i) {
      		map[i].resize(m);
      		for (int j = 0; j < m; ++j) {
      			cin >> map[i][j];
      		}
      	}
      	for (int i = 0; i < k; ++i) {
      		cin >> dir;
      		moveDice(dir);
      	}
      	return 0;
      }
백준 14226번 이모티콘|AlgorithmBOJ|Algorithm

#14226. 이모티콘

Problem

Solution

  1. 화면에 있는 이모티콘 모두 클립보드에 저장
  2. 클립보드에 있는 이모티콘 화면에 붙여넣기
  3. 화면에 있는 이모티콘 하나 삭제

클립보드에 이모티콘이 하나라도 있어야 2번 작업 가능

화면에 이모티콘이 하나라도 있어야 3번 작업 가능

1번 작업은 언제나 수행 가능

2번 작업은 화면에 있는 이모티콘 + 클립보드 이모티콘이 목표(만들어야 할 이모티콘 수)이하여야 한다.

3번 작업은 화면에 있는 이모티콘 - 1이 0이상이어야 한다. (목표 이모티콘 최소 수가 2이기에 1이상이어도 상관 없다.)

각 작업은 1초로 동일한 시간이 걸리기에 BFS로 해결한다.

  • queue에는 <화면에 있는 이모티콘 수, 클립보드에 있는 이모티콘 수>가 저
  • 중복되지 않도록 dist라는 배열에 [화면][클립보드] 첨자를 이용해 시간을 저장한다.

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
#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
queue<pair<int, int>> q;
int dist[1001][1001];
int main() {
	int n; cin >> n;
	q.push({ 1, 0 });
	while (!q.empty()) {
		int s, c;
		tie(s, c) = q.front();
		q.pop();
		if (dist[s][s] == 0) { // 화면에 있는 이모티콘 클립보드에 복사
			dist[s][s] = dist[s][c] + 1;
			q.push({ s, s });
		}
		if (s+c <= n && dist[s+c][c] == 0) { // 클립보드 화면에 붙여넣기
			dist[s + c][c] = dist[s][c] + 1;
			q.push({ s + c, c });
		}
		if (s - 1 >= 0 && dist[s - 1][c] == 0) { // 화면에 있는 이모티콘 -1
			dist[s - 1][c] = dist[s][c] + 1;
			q.push({ s - 1, c });
		}
	}
	int ans = 1e9;
	for (int i = 0; i <= n; ++i) { // 최솟값 찾기
		if (ans > dist[n][i] && dist[n][i] != 0) ans = dist[n][i];
	}
	cout << ans << "\n";
	return 0;
}
백준 13913번 숨바꼭질 4|AlgorithmBOJ|Algorithm

#13913. 숨바꼭질 4

Problem

Solution

  • BFS 탐색을 하되, 경로를 알고 있어야 하기에 path[to] = from 을 사용한다.
  • 즉, 5→6→8→10 이라면 path[10]에는 8, path[8]에는 6이 저장되어 있다.

  • 경로를 출력하기 위해 재귀함수를 사용한다.

    1
    2
    3
    4
    (5, 10) 4. 출력
    	(5, 8) 3. 출력
    		(5, 6)  2. 출력
    			(5, 5) 1. 출력

    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
    #include <iostream>
    #include <queue>
    #include <vector>
    #define MAX 100000
    using namespace std;
    int N, K;
    bool end_flag;
    int dist[MAX+1];
    vector<int> path;
    int dx[4] = { -1, 1, 0, 0 };
    int dy[4] = { 0, 0, -1, 1 };
    void Input() {
    	cin >> N >> K;
    }
    void PrintPath() {
    	for (auto e : path) cout << e << " ";
    	cout << "\n";
    }
    void BFS() {
    	queue<int> q;
    	q.push(N);
    	while (!q.empty()) {
    		int n = q.front();
    		q.pop();
    		if (n == K) return;
    		if (n > 0 && dist[n - 1] == 0) {
    			dist[n - 1] = dist[n] + 1;
    			q.push(n - 1);
    		}
    		if (n < MAX && dist[n + 1] == 0) {
    			dist[n + 1] = dist[n] + 1;
    			q.push(n + 1);
    		}
    		if (2 * n <= MAX && dist[2 * n] == 0) {
    			dist[2 * n] = dist[n] + 1;
    			q.push(2 * n);
    		}
    	}
    }
    void DFS(int n, int cnt) {
    	if (end_flag == true) return;
    	if (dist[K] == cnt && n == K) {
    		cout << dist[K] << "\n";
    		PrintPath();
    		end_flag = true;
    		return;
    	}
    	if (dist[K] == cnt) return;
    	if (n > 0) {
    		path.push_back(n - 1);
    		DFS(n - 1, cnt + 1);
    		path.pop_back();
    	}
    	if (n < MAX) {
    		path.push_back(n +1);
    		DFS(n + 1, cnt + 1);
    		path.pop_back();
    	}
    	if (2 * n <= MAX) {
    		path.push_back(2 * n);
    		DFS(2 * n, cnt + 1);
    		path.pop_back();
    	}
    }
    void Solve() {
    	BFS();
    	path.push_back(N);
    	DFS(N, 0);
    }
    int main() {
    	Input();
    	Solve();
    	return 0;
    }

    BFS + DFS로 구하니 시간초과 (BFS로 depth를 구하고 그 depth만큼 DFS를 수행하도록 하였다.)

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
#include <iostream>
#include <queue>
#include <vector>
#define MAX 100000
using namespace std;
int N, K;
int dist[MAX + 1];
int path[MAX + 1];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
void Input() {
	cin >> N >> K;
}
void PrintPath(int from, int to) {
	if (from != to) {
		PrintPath(from, path[to]);
	}
	cout << to << " ";
}
void BFS() {
	queue<int> q;
	q.push(N);
	while (!q.empty()) {
		int n = q.front();
		q.pop();
		if (n == K) return;
		if (n > 0 && dist[n - 1] == 0) {
			dist[n - 1] = dist[n] + 1;
			path[n - 1] = n;
			q.push(n - 1);
		}
		if (n < MAX && dist[n + 1] == 0) {
			dist[n + 1] = dist[n] + 1;
			path[n + 1] = n;
			q.push(n + 1);
		}
		if (2 * n <= MAX && dist[2 * n] == 0) {
			dist[2 * n] = dist[n] + 1;
			path[2 * n] = n;
			q.push(2 * n);
		}
	}
}
void Solve() {
	BFS();
	cout << dist[K] << "\n";
	PrintPath(N, K);
}
int main() {
	Input();
	Solve();
	return 0;
}
백준 13460번 구슬 탈출 2|AlgorithmBOJ|Algorithm

#13460. 구슬 탈출 2

Problem

Solution

  • 시뮬레이션 문제이다.
  • 어떤 방향으로 기울일지 정해야 한다. (모든 경우를 구해야 한다. - 재귀 사용)
    이전 방향과 반대되는 방향으로 이동할 필요는 없다.
  • 맵을 갱신할 필요는 없고 구슬의 위치만 변경하면 된다.
  • 각 경우마다 구슬의 위치를 다음 작업에 넘겨주어야 한다. (재귀 함수 인자로 넘기기)
  • 기울이기 재귀함수
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    Move(이동 횟수, 이전 방향, 빨간 구슬 위치, 파란 구슬 위치)
     if 이동 횟수 > 10  return
     if 파란 구슬이 구멍에 들어간 경우 return
     if 빨간 구슬만 구멍에 들어간 경우 최솟값 갱신 return
     4 방향 이동
      벽이 아닐 때까지, 구멍 일 때까지 이동
      // 빨간 구슬 이동
      // 파란 구슬 이동
      이동이 끝나면
      if 위치가 겹칠 때
         if 구멍이면 Move(이동 횟수 + 1, 방향, 위치)
         else 
            같은 행일 때
    				같은 열일 때
    				위치 이동
            Move(이동횟수 +1, 방향, 위치)
      else
    		 Move(이동횟수 +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
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
#include <iostream>
using namespace std;
int N, M, ans = 1e9;
int g_x, g_y;
char board[11][11];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int count_dir[4] = { 1, 0, 3, 2 };
struct Red {
	int x, y;
};
struct Blue {
	int x, y;
};
void Move(int cnt, int prior_dir, Red r, Blue b) {
	if (cnt > 10) return;
	if (b.x == g_x && b.y == g_y) return; // 파란 구슬 구멍 통과
	if (r.x == g_x && r.y == g_y) { // 빨간 구슬만 구멍 통과
		if (ans > cnt) ans = cnt;
		return;
	}
	for (int dir = 0; dir < 4; ++dir) {
		Red nr = { r.x, r.y }; Blue nb = { b.x, b.y }; // next
		if (prior_dir != -1 && count_dir[prior_dir] == dir) continue;
		while (true) {
			if (board[nr.x + dx[dir]][nr.y + dy[dir]] == '#') break;
			nr.x += dx[dir];
			nr.y += dy[dir];
			if (board[nr.x][nr.y] == 'O') break;
		}
		while (true) {
			if (board[nb.x + dx[dir]][nb.y + dy[dir]] == '#') break;
			nb.x += dx[dir];
			nb.y += dy[dir];
			if (board[nb.x][nb.y] == 'O') break;
		}
		if (nr.x == nb.x && nr.y == nb.y) { // 겹칠 때
			if (board[nr.x][nr.y] == 'O') Move(cnt + 1, dir, nr, nb);
			else {
				if (r.x == b.x) { // 같은 행
					if (r.y < b.y) { // R B
						if (dir == 2) nb.y++;
						else if (dir == 3) nr.y--;
					}
					else { // B R
						if (dir == 2) nr.y++;
						else if (dir == 3) nb.y--;
					}
				}
				else if (r.y == b.y) { // 같은 열
					if (r.x < b.x) { // R이 B보다 위
						if (dir == 0) nb.x++;
						else if (dir == 1) nr.x--;
					}
					else { // R이 B보다 아래
						if (dir == 0) nr.x++;
						else if (dir == 1) nb.x--;
					}
				}
				Move(cnt + 1, dir, nr, nb);
			}
		}
		else {
			Move(cnt + 1, dir, nr, nb);
		}
	}
}
int main() {
	cin >> N >> M;
	Red r; Blue b;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			cin >> board[i][j];
			if (board[i][j] == 'O') {
				g_x = i; g_y = j;
			}  
			else if (board[i][j] == 'R') {
				r.x = i; r.y = j;
			}
			else if (board[i][j] == 'B') {
				b.x = i; b.y = j;
			}
		}
	}
	Move(0, -1, r, b);
	if (ans == 1e9) cout << -1 << "\n";
	else cout << ans << "\n";
	return 0;
}

문제 풀고나서 찾아본 깔끔한 코드

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
#include<cstdio>
int n, m;
int rx, ry, bx, by;
char a[11][11];
int ans = 11;
void go(int rx, int ry, int bx, int by, int mx, int my, int cnt){
	if (cnt >= ans) return;
	int rm = 0, bm = 0;
	if (mx != my){
		while (a[bx + mx][by + my] - '#'){
			bx += mx;
			by += my;
			bm++;
			if (!(a[bx][by] - 'O'))
				return;
		}
		while (a[rx + mx][ry + my] - '#'){
			rx += mx;
			ry += my;
			rm++;
			if (!(a[rx][ry] - 'O')){
				ans = ans < cnt ? ans : cnt;
				return;
			}
		}
	}
	if (rx == bx && ry == by)
		if (rm < bm)
			bx -= mx, by -= my;
		else
			rx -= mx, ry -= my;
	if (mx == 0){
		go(rx, ry, bx, by, 1, 0, cnt + 1);
		go(rx, ry, bx, by, -1, 0, cnt + 1);
	}
	if (my == 0){
		go(rx, ry, bx, by, 0, 1, cnt + 1);
		go(rx, ry, bx, by, 0, -1, cnt + 1);
	}
}
int main(){
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%s", a[i]);
	for (int i = 1; i < n - 1; i++){
		for (int j = 1; j < m - 1; j++){
			if (a[i][j] == 'R')
				rx = i, ry = j;
			if (a[i][j] == 'B')
				bx = i, by = j;
		}
	}
	go(rx, ry, bx, by, 0, 0, 0);
	printf("%d", ans < 11 ? ans : -1);
}