(파이썬) 백준 3085번 "사탕 게임"
# 팁 1
이 문제를 풀면서 알게 된, 이 문제를 풀 때 도움이 되는 팁 몇 가지를 소개해보겠습니다.
첫 번째 팁은 위와 같이 입력 형식으로 2차원 배열이 주어졌을 때, 이를 편리하게 입력받는 방법입니다.
n = int(input())
board = [list(input()) for _ in range(n)]이렇게 코드를 작성하면, n개의 행으로 이뤄진 2차원 배열을 입력받을 수 있습니다.
행의 개수가 n개이면 되지 열의 개수까지 n개일 필요는 없습니다. 심지어, 모든 행이 다른 열의 개수를 가지고 있어도 오류가 뜨지 않는 코드입니다.
# 팁 2
두 번째 팁은 글로벌 변수(전역 변수)를 사용하는 방법입니다.
val = 1
def f():
val = 2위 코드에서 첫 번째로 등장한 변수 val은 두 번째로 등장한 val와 전혀 다른 변수입니다. 함수 안에서 선언된 변수(정확히는 immutuable한 변수)는 함수 밖에 똑같은 이름의 변수가 있더라도 서로 영향을 주지 않습니다.
def 안에 선언된 val은 그 영역 안에서만 사용할 수 있는 지역 변수이기 때문입니다.
하지만 아래와 같이 코드를 짜면 이야기가 다릅니다.
val = 1
def f():
global val = 2def 안에 선언되어 지역변수였어야 할 val 앞에 global 이라는 예약어가 붙음으로써 전역 변수가 되었습니다. 이렇게 되면 함수 안에 있는 val는 함수 밖에 있는 val와 정확히 똑같은 대상을 가리키게 됩니다.
# 팁 3
다음은 두 변수에 담긴 값을 서로 바꿔치기 하는 방법을 알아보겠습니다.
널리 알려져 있는, 두 변수(a, b)에 담긴 값을 바꿔치기 하는 전형적인 방법은 아래 코드와 같습니다.
하지만 파이썬의 튜플 자료형을 활용하면 더 간단하게 값을 바꿔치기 할 수 있습니다.
tmp = a
a = b
b = tmp
아래와 같이 단 한 줄로 쓸 수 있습니다. 원리가 궁금하신 분들은 튜플 자료형에 대해서 알아보시길 바랍니다.
a, b = b, a
# 답 1
n = int(input())
board = [list(input()) for _ in range(n)]
ans = 1
def search():
global ans
for i in range(n):
cnt = 1
for j in range(1, n):
if board[i][j-1] == board[i][j]:
cnt += 1
ans = max(ans, cnt)
else:
cnt = 1
for j in range(n):
cnt = 1
for i in range(1, n):
if board[i-1][j] == board[i][j]:
cnt += 1
ans = max(ans, cnt)
else:
cnt = 1
for i in range(n):
for j in range(n):
if j + 1 < n:
board[i][j], board[i][j + 1] = board[i][j + 1], board[i][j]
search()
board[i][j], board[i][j + 1] = board[i][j + 1], board[i][j]
if i + 1 < n:
board[i][j], board[i + 1][j] = board[i + 1][j], board[i][j]
search()
board[i][j], board[i + 1][j] = board[i + 1][j], board[i][j]
print(ans)
# 답 2
n = int(input())
board = [list(input()) for _ in range(n)]
ans = 1
# x 좌표의 세로 줄을 검사
def search_col(x):
global ans
cnt = 1
for i in range(n - 1):
if board[i][x] == board[i + 1][x]:
cnt += 1
ans = max(ans, cnt)
else:
cnt = 1
return ans
# y 좌표의 가로 줄을 검사
def search_row(y):
global ans
cnt = 1
for i in range(n - 1):
if board[y][i] == board[y][i + 1]:
cnt += 1
ans = max(ans, cnt)
else:
cnt = 1
return ans
# 바꾸기 전 상태에서의 최댓값
for i in range(n):
ans = max(ans, search_row(i), search_col(i))
for y in range(n):
for x in range(n):
# 가로로 바꾸기
if y < n - 1 and board[y][x] != board[y + 1][x]:
board[y][x], board[y + 1][x] = board[y + 1][x], board[y][x]
ans = max(ans, search_col(x), search_row(y + 1), search_row(y))
board[y][x], board[y + 1][x] = board[y + 1][x], board[y][x]
# 세로로 바꾸기
if x < n - 1 and board[y][x] != board[y][x + 1]:
board[y][x], board[y][x + 1] = board[y][x + 1], board[y][x]
ans = max(ans, search_col(x), search_row(y), search_col(x + 1))
board[y][x], board[y][x + 1] = board[y][x + 1], board[y][x]
print(ans)답1의 코드는 시간이 다소 오래 걸립니다. 변동이 일어나는 칸은 겨우 두 칸뿐이므로 그 두 칸이 속한 행과 열, 총 3줄만 살펴봐도 되기 때문입니다. 답2는 변동이 일어날 때마다 변동이 일어난 3줄만 확인하도록 하여 실행 속도를 단축시킨 코드입니다.
