[백준] No.3085_사탕 게임 01
3085번: 사탕 게임
예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.
www.acmicpc.net
처음에 문제를 보고 이해가 살짝 안 됐다.
"고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져있는 가장 긴 연속 부분을 고른다." ...?
왜 문장을 이어주는 말로 '이제'를 썼는지도 잘 모르겠고, 가장 긴 증가하는 부분 수열 문제인가? 그럼 DP인데...
하다가 '아 그냥 두 위치를 바꿨을 때, 가장 긴 부분이 생기는 곳을 찾으라는 이야기구나'를 알 수 있었다.
LIS 문제와는 다른 점이 있다. LIS는 요소들이 고정된 배열에서 값을 찾아내는 DP 문제이다.
이 문제는 어느 부분을 바꿔야 '가장 긴 연속 부분'이 나오는지 모르기에 일일이 바꿔야 하는 브루트포스 문제이다.
ABAB
BABA
ABAB
BABA 라는 2차원 배열이 있다고 가정
1. [0][0] A의 입장에서 [0][1] B와 바꾸기
2. [0][1] B의 입장에서 [0][0] A와 바꾸기브루트포스 문제라서 각 부분을 일일이 바꾸고 풀어야 한다.
하지만 브루트포스라고 비효율적으로 검사하는 알고리즘이 아니다. 모든 경우의 수를 검사하는 알고리즘인 거지.
보면 1번의 케이스와 2번의 케이스는 동일한 결과가 나오는 것을 알 수 있다.
그럼 어차피 결과가 같은데 굳이 한 번 더 검사를 할 이유가 없지 않나?
라고 하는 생각을 기반으로 크게 2가지 부분을 유의하면서 코드를 생각했다.
첫 번째는 바꿔야 하는 원소들에 대해서 생각했다.
(왼쪽의 그림처럼) 위에서 잠깐 언급했듯이 두 부분은 서로 같은 결과를 낳는다.
원소 x를 기준으로 상하좌우를 바꾸는 것은, 상하좌우의 입장에서 원소 x와 바꾸는 것과 동일하다.
그럼 가장 많은 부분을 중복으로 갖는 원소는 어디일까? 가운데이다.
가운데를 기점으로 상하좌우는 제외하고 그 다음을 체크하며 끝까지 확인해보았다.
그랬더니 가운데 그림같은 체스판 형태가 되었다. 여기서 봐야 하는 곳은 첫 번째이다.
[0][0]의 인덱스, 즉 가장 처음의 원소를 기준으로 뛰엄뛰엄 나아가면 되는 것이다.
많은 문제를 풀어보았다면 생각나는 문제가 하나 있을 것이다. 1018번의 체스판 다시 칠하기 문제이다.
행과 열의 인덱스가 짝수인 곳만 확인하면 되는 문제였다.
두 번째는 바꾸고 난 뒤 확인할 행과 열에 대해서 생각했다.
오른쪽 그림처럼 3번째 열의 2, 3번째 행의 숫자들을 바꿨다고 가정해보자.
이때 모든 위치를 브루트포스로 확인을 할 필요가? 없다.
바꾼 행과 열에 대해서만 확인을 해주면 된다.
따라서 바뀐 부분을 검사할 CheckRow() 함수와 CheckCol() 함수를 만들어서 검사를 진행해준다.
# ---------- Import ----------
import sys
input = sys.stdin.readline늘 시간 초과에 유의해야 하는 브루트 포스 문제이다.
그게 아니더라도 위의 Import는 습관적으로 코드를 작성하고 있다.
이젠 당연하니 자세한 설명은 생략한다.
# ---------- Function ----------
# Function that check only input row
def CheckRow(lst: list, rowNum: int) -> int:
count, maxCount = 1, 1
first = lst[rowNum][0]
for i in range(1, len(lst)):
if first == lst[rowNum][i]:
count += 1
else:
first = lst[rowNum][i]
count = 1
maxCount = max(maxCount, count)
return maxCount특정 행만을 확인하여 가장 긴 부분을 검사하는 함수이다.
문제에서 빨간색은 C이니 파란색은 P이니 던져주었지만 아무 상관이 없다.
그저 지금 원소를 전과 비교했을 때 같으면 +1 아니면 1로 초기화하면 된다.
# ---------- Function ----------
# Function that check only input col
def CheckCol(lst: list, colNum: int) -> int:
count, maxCount = 1, 1
first = lst[0][colNum]
for i in range(1, len(lst)):
if first == lst[i][colNum]:
count += 1
else:
first = lst[i][colNum]
count = 1
maxCount = max(maxCount, count)
return maxCount특정 열만을 확인하여 가장 긴 부분을 검사하는 함수이다.
행만을 검사하는 CheckRow 함수와 2차원 배열 인덱스만 달라졌다. 나머지는 전부 동일하다.
그래서 두 함수를 합쳐서 Checking(lst, idxNum, row_or_col)이라는 함수로 만들까 했다.
하지만 그럼 if문으로 row인지 col인지 확인하는 구문이 필요하다.
또한 row인지 col인지에 따라 들어가는 인덱스들도 따로 처리를 해줘야 했다.
어렵지는 않지만 직관적이지 않다고 생각했다. 함수는 최소 기능 단위로 분류해야 한다.
그래서 유사하지만 굳이 두 함수를 합치지 않고 독립적으로 작성해주었다.
# ---------- Main ----------
length = int(input())
candy = [list(input().rstrip()) for _ in range(length)]
# UP, DN, LFT, RGT
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
answer = 1 # Initialization길이(length)와 2차원 배열(candy)을 입력받는다.
반복문으로 네 방향을 탐색하기 위하여 dx, dy 배열을 선언하였다.
그리고 정답(answer) 변수는 1로 초기화한다.
0이 아니라 1인 이유는, 글자가 0개가 아니라 1개가 늘 있기 때문이다.
# ---------- Main ----------
# Brute force
for row in range(length):
for col in range(length):
# Not checking all element
if (row + col) % 2 == 0:
# Checking 4 directions
for i in range(4):
nx = dx[i] + row
ny = dy[i] + col
if 0 <= nx < length and 0 <= ny < length:
# swap
candy[row][col], candy[nx][ny] = candy[nx][ny], candy[row][col]
# Only check, changing row and col location
answer = max(answer, CheckRow(candy, row))
answer = max(answer, CheckRow(candy, nx))
answer = max(answer, CheckCol(candy, col))
answer = max(answer, CheckCol(candy, ny))
# rollback
candy[row][col], candy[nx][ny] = candy[nx][ny], candy[row][col]
print(answer)이 글의 핵심 코드이다. 이중 반복문으로 모든 원소들을 하나하나 확인한다.
이때 row + col 인덱스가 짝수일 때만 네 방향 검사를 진행한다.
검사할 네 방향이 정해진 범위 내에 있다면 swap, check, rollback의 단계를 거친다.
30분이 채 되기 전에 한 번에 코드 풀이에 성공했다.
처음에 살짝 막혔던 것을 생각하면 의외로 빠르게 정답에 다가갔다.
다른 사람들의 풀이를 보니, 현재 원소를 기준으로 오른쪽과 아래만을 비교ㆍ교환하는 식으로 코드를 작성했다.
이런 방법이 조건문을 더 줄일 수 있고, 전체적으로 일관된 코드를 작성할 수 있겠다는 생각이 들었다.
아이디어 측면에서 더 좋은 방안을 생각해봐야 겠다.