[백준알고리즘] 3085번: 사탕 게임 -Python

[백준알고리즘] 3085번: 사탕 게임 -Python

https://www.acmicpc.net/problem/3085

3085번: 사탕 게임

브루트 포스문제이다.

 

문제가 약간 헷갈리는데, 반드시 색이 다른 두 사탕이 인접한 칸이 하나 이상 존재한다. 하지만 반드시 색이 다른 두 칸을 교환하는 것은 아니다. 문제에는 다음과 같이 색이 다른 인접한 두 칸을 교환하는 것으로 나와있는데, 이렇게 하면 틀렸다고 나오니 같은 색이라도 교환할 수 있는 것으로 생각해야 한다.

 

나머지는 브루트 포스로 구해야 할 길이를 잘 구하기만 하면 된다.

처음에는 세로로 교환한 경우에는 가로의 길이만 확인하고, 가로로 교환한 경우에는 세로의 길이만 확인하면 되는 줄 알았다. 하지만 교환한 방향으로도 길이를 확인해야 한다.

 

가로로 교환하는 경우만 확인하게 되면 (i, j)와 (i, j+1)이 교환한 상태일 것이다. 이렇게 가로로 교환하게 되면 (i, j)의 세로열로 가장 길게 이어지는 사탕과 (i, j+1)의 세로열로 가장 길게 이어지는 사탕의 길이를 구한다.

그리고 (i, j)와 (i, j+1)의 교환한 사탕이 서로 다른 경우 (i, j)에서 왼쪽 방향으로 가장 긴 사탕의 길이를 구하고, (i, j+1)의 오른쪽 방향으로 가장 긴 사탕의 길이를 구한다. 이 경우 (i, j)와 (i, j+1)의 교환한 사탕이 같은 색이라면 같은 색의 일렬이라는 것을 확인해야 한다.

 

이렇게 구한 각각의 길이들 중에서 가장 긴 길이를 확인하면 된다.

n = int(input())
candy = [list(input().rstrip()) for _ in range(n)]
dx, dy = [1, 0], [0, 1]

def check(d, i, j):
    x, y = i+dx[d], j+dy[d]
    cnt1 = cnt2 = cnt3 = cnt4 = 1
    if d == 0: # d = 0, swap vertical
        # check horizontal
        for k in range(j+1, n):
            if candy[i][j] != candy[i][k]: break
            cnt1 += 1
        for k in range(j-1, -1, -1):
            if candy[i][j] != candy[i][k]: break
            cnt1 += 1
        
        for k in range(y+1, n):
            if candy[x][y] != candy[x][k]: break
            cnt2 += 1
        for k in range(y-1, -1, -1):
            if candy[x][y] != candy[x][k]: break
            cnt2 += 1
        
        # check vertical
        for k in range(i-1, -1, -1):
            if candy[i][j] != candy[k][j]: break
            cnt3 += 1
        for k in range(x+1, n):
            if candy[x][y] != candy[k][y]: break
            cnt4 += 1
    else: # d = 1, swap horizontal
        # check vertical
        for k in range(i+1, n):
            if candy[i][j] != candy[k][j]: break
            cnt1 += 1
        for k in range(i-1, -1, -1):
            if candy[i][j] != candy[k][j]: break
            cnt1 += 1
        
        for k in range(x+1, n):
            if candy[x][y] != candy[k][y]: break
            cnt2 += 1
        for k in range(x-1, -1, -1):
            if candy[x][y] != candy[k][y]: break
            cnt2 += 1
        
        # check horizontal
        for k in range(j-1, -1, -1):
            if candy[i][j] != candy[i][k]: break
            cnt3 += 1
        for k in range(y+1, n):
            if candy[x][y] != candy[x][k]: break
            cnt4 += 1
    if candy[i][j] == candy[x][y]:
        cnt3 += cnt4
    return max(cnt1, cnt2, cnt3, cnt4)

ans = 0
for i in range(n):
    for j in range(n):
        for d in range(2):
            x, y = i+dx[d], j+dy[d]
            if x < n and y < n:
                candy[i][j], candy[x][y] = candy[x][y], candy[i][j]
                ans = max(ans, check(d, i, j))
                candy[i][j], candy[x][y] = candy[x][y], candy[i][j]
print(ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다