📌 문제 탐색하기
- N X N 크기의 보드에 4가지 종류의 사탕(C, P, Z, Y)이 놓여져 있다.
- 색이 다른 인접한 두 사탕의 위치를 바꾼 후, 보드에서 같은 행이나 열에 같은 색상의 사탕이 연속으로 놓여져있는 최대 개수를 세어야 한다.
💡 알고리즘 선택
- 브루트 포스 알고리즘을 활용하여 보드 전체에 대해서 사탕 교환 과정을 처리해야 할 것 같다.
- 한 좌표에 대해서 상, 하, 우 범위에 자신과 다른 색의 사탕이 있다면 둘의 위치를 바꾸고, 현재 보드판에 같은 색상의 사탕이 직선 상에 몇개 놓여져 있는지 확인하는 함수를 구현하여 최대 값을 찾아야 할 것 같다.
📌 코드 설계하기
1. 문제의 input을 입력 받아서 원본 보드판을 구현한다.
2. 원본 보드판에서 일렬로 놓여진 사탕의 최대 개수를 구한다.
3. 보드판에 같은 색으로 놓여진 사탕이 일직선 상에 몇개 있는지 판별하는 check_board 함수를 구현한다.
(바뀐 사탕들이 포함된 열과 행만 판별하도록 구현했음)
4. 보드판을 차례대로 돌면서 오른쪽, 아래쪽 범위에 자신과 다른 사탕이 놓여져 있다면 둘의 위치를 바꾸고, check_board 함수를 호출하여 바뀐 사탕들이 포함된 행과 열에 놓여진 사탕의 최대 개수를 저장한다.
(오른쪽 방향으로 순차적으로 탐색하므로 왼쪽, 위쪽방향은 계산X)
5. 보드판의 전체 범위를 돌고, 함수를 통해 구한 사탕의 최대 개수를 호출한다.
📌 시도 회차 수정 사항 (Optional)
1회차
기존에는 사탕의 위치를 변경하고, 전체 보드판에 대해서 일자로 놓인 사탕의 개수를 세도록 했었으나, 수행 시간을 단축하고 싶어서 바뀐 사탕이 위치한 행과 열에서만 개수 판단을 하도록 수정하였다.
기존 방식에 비해서 수정한 방식이 수행 시간이 훨씬 빠른걸 볼 수 있음.
기존 코드
n = int(input())
board = [list(input()) for _ in range(n)]
answer = 1
def check_board():
global answer
for i in range(n):
row_count = 1
col_count = 1
for j in range(n - 1):
# 행 검사
if board[i][j] == board[i][j+1]:
row_count += 1
else:
row_count = 1
# 열 검사
if board[j][i] == board[j+1][i]:
col_count += 1
else:
col_count = 1
answer = max(answer, row_count, col_count)
dx = [0, 1] # 오른쪽 방향으로 순차적으로 탐색하므로 왼쪽, 위쪽 방향은 구하지 않음
dy = [1, 0]
for i in range(n):
for j in range(n):
currentColor = board[i][j]
for k in range(2):
nx = i + dx[k]
ny = j + dy[k]
if n > nx >= 0 and n > ny >= 0 and currentColor != board[nx][ny]:
board[i][j], board[nx][ny] = board[nx][ny], board[i][j]
check_board()
board[i][j], board[nx][ny] = board[nx][ny], board[i][j]
print(answer)📌 정답 코드
n = int(input())
board = [list(input()) for _ in range(n)]
answer = 1
# 원본 보드에서 개수 세기기
for i in range(n):
row_count = 1
col_count = 1
for j in range(n - 1):
# 행 검사
if board[i][j] == board[i][j+1]:
row_count += 1
else:
row_count = 1
# 열 검사
if board[j][i] == board[j+1][i]:
col_count += 1
else:
col_count = 1
answer = max(answer, row_count, col_count)
def check_board(i, j, nx, ny, k):
global answer
if k == 0: # 오른쪽 사탕과 교환
a = board[i]
b = [r[j] for r in board]
c = [r[ny] for r in board]
elif k == 1: # 아래쪽 사탕과 교환
a = board[i]
b = board[nx]
c = [r[j] for r in board]
data = [a, b, c]
for s in data:
count = 1
for idx in range(n-1):
if s[idx] == s[idx+1]:
count += 1
else:
count = 1
answer = max(answer, count)
dx = [0, 1] # 오른쪽 방향으로 순차적으로 탐색하므로 왼쪽, 위쪽 방향은 구하지 않음
dy = [1, 0]
for i in range(n):
for j in range(n):
currentColor = board[i][j]
for k in range(2):
nx = i + dx[k]
ny = j + dy[k]
if n > nx >= 0 and n > ny >= 0 and currentColor != board[nx][ny]:
board[i][j], board[nx][ny] = board[nx][ny], board[i][j]
check_board(i, j, nx, ny, k)
board[i][j], board[nx][ny] = board[nx][ny], board[i][j]
print(answer)