meatsby.github.io

BOJ 3085 - 사탕 게임

2 min read

풀이

브루트포스 알고리즘 구현 문제이다.

이 문제를 해결하기 위해선 2가지 기능을 구현해야한다.

  1. 인접하는 사탕의 위치를 서로 교환하는 기능

  2. 행 또는 열에서 가장 긴 연속 부분을 찾는 기능

2번 기능은 함수로 구현하고 1번 기능이 돌아갈 때마다 2번 기능을 활용하는 식으로 코드를 짰다.

1번 기능을 구현할 때 알 수 있는 점은 각 칸을 검사할 경우 우측과 하단만 고려하면 된다는 것이다.

소스코드

import sys
 
input = sys.stdin.readline
 
 
def inspect(c, n):
    cnt = 1
    for i in range(n):
        cnt_row = 1
        cnt_col = 1
        for j in range(n - 1):
            # hotizontal inspection
            if c[i][j] == c[i][j + 1]:
                cnt_row += 1
            else:
                cnt = max(cnt, cnt_row)
                cnt_row = 1
            # vertical inspection
            if c[j][i] == c[j + 1][i]:
                cnt_col += 1
            else:
                cnt = max(cnt, cnt_col)
                cnt_col = 1
 
        cnt = max(cnt, cnt_row, cnt_col)
    return cnt
 
 
n = int(input())
c = [list(input().rstrip()) for _ in range(n)]
ans = 0
 
for i in range(n):
    for j in range(n - 1):
        # horizontal exchange
        if c[i][j] != c[i][j + 1]:
            c[i][j], c[i][j + 1] = c[i][j + 1], c[i][j]
            ans = max(ans, inspect(c, n))
            c[i][j], c[i][j + 1] = c[i][j + 1], c[i][j]
        # vertical exchange
        if c[j][i] != c[j + 1][i]:
            c[j][i], c[j + 1][i] = c[j + 1][i], c[j][i]
            ans = max(ans, inspect(c, n))
            c[j][i], c[j + 1][i] = c[j + 1][i], c[j][i]
 
print(ans)

References

Graph View