백준 3085. 사탕 게임
알고리즘 기초 문제 중 브루트포스 기초 문제(500)
1. 간단 설명
NxN 맵에 사탕이 주어진다
사탱의 색이 다른 인접한 두 칸을 고른 뒤, 그 두칸을 서로 교환한다
모두 같은 색으로 이루어져있는 가장 긴 연속 부분(행 또는 열)의 사탕의 개수만큼 먹는다
가장 많이 먹을 수 있는 개수를 고르기
2. 예시
1
2
3
4
3
CCP
CCP
PPC
[2,3] <-> [3,3]을 교환해서 2열을 CCC 만들어 먹기
혹은 [3,2] <-> [3,3]을 교환해서 2행을 CCC만들어 먹기
1
2
3
4
5
4
PPPP
CYZY
CCPY
PPCC
1행 건들지 않고 다른곳 아무데나 교환해서 PPPP 먹기
1
2
3
4
5
6
5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ
[3,1] <-> [3,2] 교환해서 1열에 YCCCC 만들어 먹기
3. 알고리즘
크게 두 부분을 구현하는 문제로 볼 수 있다
맵에서 한 점을 골라 교환하는 부분
가장 긴 부분을 찾는 부분
먼저 맵에서 한 점을 골라 교환을 시도하는 부분을 자세히 보면
map[y][x]에서 교환할 수 있는 부분은 인접한 4방향으로
1
2
3
4
5
[y-1][x]
↑
[y][x-1] ← [y][x] → [y][x+1]
↓
[y+1][x]
으로 볼 수 있다
그런데 map[2][2]에서 map[1][2]를 교환하여 체크해본 것과
map[1][2]에서 map[2][2]를 교환해 체크해보는 것은 어짜피 같은 결과이므로
우측과 하단만 체크하면 된다
두번째로, 가장 긴 부분을 찾는 부분은
맵에서 교환이 이루어진 상태에서, 가장 긴 부분을 행과 열에서 각각 찾으면 된다
행을 기준으로 설명하면 현재 map[y][x]와 map[y][x+1]가 같은 사탕이라면, 1증가 해주고,
다음으로 넘어가는 식으로 체크한다
이런식으로 사탕의 개수가 가장 클 때를 기록해두고 이를 출력한다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1. N과 맵 정보 입력받기
2. 0,0부터 시작하여, 우측과 하단을 교환해가면서 체크 시작
2-1. 오른쪽과 교환 시도
2-1-1. 만약 오른쪽 끝이라 더이상 교환할 사탕이 없으면 패스
2-1-2. map[y][x]와 map[y][x+1]을 교환
2-1-3. 현재 맵 상태를 바탕으로 사탕 최대 개수 체크
2-1-3-1. 행의 사탕의 최대 개수를 체크한다
2-1-3-1-1. 현재 사탕과 오른쪽 사탕이 같다면 cnt를 1 증가시킴
2-1-3-1-2. 다르다면 cnt를 1로 설정하고, 최대값을 비교하여 저장함
2-1-3-2. 열의 사탕의 최대 개수를 체크한다
2-1-4. 맵을 다시 초기상태로 원상복구
2-2. 아래쪽과 교환 시도
2-2-1. 만약 아래쪽 끝이라 더이상 교환할 사탕이 없으면 패스
2-2-2. map[y][x]와 map[y+1][x]를 교환
2-2-3. 현재 맵 상태를 바탕으로 사탕 최대 개수 체크
2-2-3-1. 행의 사탕의 최대 개수를 체크한다
2-2-3-1-1. 현재 사탕과 오른쪽 사탕이 같다면 cnt를 1 증가시킴
2-2-3-1-2. 다르다면 cnt를 1로 설정하고, 최대값을 비교하여 저장함
2-2-4. 맵을 다시 초기상태로 원상복구
구현 문제다보니 4중 for문으로 돌아가게 되었다
시간 복잡도는
교환 하는 부분이 NxNx2 로 O(N^2),
체크하는 부분이 각 행과 열에 대해 최대 N번 비교하므로 O(N^2),
전체 시간 복잡도는 O(N^4)이다.
그래도 맵 자체가 최대 50x50으로 작은편이여서 6,250,000번 수행하므로, 1초 내에는 충분히 가능하다
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
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
#include <iostream>
using namespace std;
int N;
char map[51][51];
int longest = 0;
// 가장 긴 단어를 찾는 함수
void check() {
// 가로 체크
for (int y = 0; y < N; y++) {
int cnt = 1;
for (int x = 0; x < N; x++) {
char cur = map[y][x];
char next = map[y][x + 1];
if (cur == next) cnt++;
else {
if (cnt > longest) longest = cnt;
cnt = 1;
}
}
}
// 세로 체크
for (int x = 0; x < N; x++) {
int cnt = 1;
for (int y = 0; y < N; y++) {
char cur = map[y][x];
char next = map[y + 1][x];
if (cur == next) cnt++;
else {
if (cnt > longest) longest = cnt;
cnt = 1;
}
}
}
}
int main() {
// freopen_s(new FILE*, "input.txt", "r", stdin);
// 1. input
cin >> N;
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
cin >> map[y][x];
}
}
// 2. 하나씩 교환하고 체크해봄
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
// 2-1. 오른쪽 시도
if (x + 1 < N) {
swap(map[y][x], map[y][x + 1]);
check();
swap(map[y][x], map[y][x + 1]);
}
if (y + 1 < N) {
swap(map[y][x], map[y + 1][x]);
check();
swap(map[y][x], map[y + 1][x]);
}
}
}
cout << longest;
return 0;
}
4중 for문밖에 답이 떠오르지 않아, 내가 모르는 다른 알고리즘이 있을까 했는데
그냥 구현 문제였다
특히 배열의 인덱스를 다루는 부분이 햇갈렸다
다른 풀이도 찾아보고 싶었으나, 대부분 4중 for문으로 푼 모양
이럴때마다 Leetcode 유료결제를 해야하나 고민된다