[알고리즘] 사탕게임 - dfs

1. 문제

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

 

 

2. 풀이

중요 point 1) n*n 모든 값들을 4가지 방면으로 switching 해본다.

-> change() 로 값이 다른지 확인하고 boolean으로 응답하기

 

중요 point 2) switching이 된다면, 같은 값을 가진 가장 긴 행/열을 구할때, 현재 2차원 index로부터 뒤의 모든 값들을 확인하지 말고 바로 앞에 있는 값이랑만 비교하면서 max값, tmp값 update 해주기

-> calc() 참조!

 

중요 point 3) switching 하고 max_val 값 update했으면, 다시 원래자리로 복구해주기

 

 

3. 코드

n = int(input())

arr = [
    list(input())
    for _ in range(n)
]

dxs, dys = [-1,1,0,0],[0,0,-1,1]

def in_range(x,y):
    return 0<=x<n and 0<=y<n

def change(x,y, nx,ny):
    if not in_range(nx,ny):
        return False
    
    if arr[x][y] != arr[nx][ny]:
        return True
    return False

def calc():
    res = 0

    # 행
    for i in range(n):
        tmp = 1  
        for j in range(1, n):
            if arr[i][j] == arr[i][j-1]:
                tmp += 1
                res = max(res, tmp)
            else:
                tmp = 1

    # 열
    for j in range(n):
        tmp = 1  
        for i in range(1, n):
            if arr[i][j] == arr[i-1][j]:
                tmp += 1
                res = max(res, tmp)
            else:
                tmp = 1

    return res


max_val = 0
for x in range(n):
    for y in range(n):
        for dx,dy in zip(dxs, dys):
            nx,ny = x + dx, y + dy

            if not change(x,y, nx,ny):
                continue

            arr[x][y], arr[nx][ny] = arr[nx][ny], arr[x][y]

            max_val = max(max_val, calc())

            arr[nx][ny], arr[x][y] = arr[x][y], arr[nx][ny]

print(max_val)