백준_3085 (사탕 게임_실버3)

RostoryT·2022년 6월 27일

백준 브루트포스

Brute force

목록 보기

2/18

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

캔디크러쉬같은 느낌인듯
처음에 삽질을 너무 많이 했음
어떻게 풀어야 할지, 처음 접하니까 감이 안와서 DFS처럼 풀면 되겠거니 했다가 DFS의 조건들을 하나씩 쳐내다보니 이런 결과물이 나옴

무식하게 첫 접근

아이디어

A함수(열ver, 행ver 두 가지로 진행)
- 행/열 직선으로만 max를 지정하니까
- 브루트포스로 시작점 잡고 한칸씩 이동하면서
- 행 행 행 먼저 서치하고
- 열 열 열 서치
- 같은 문자면
  - visit_next = visit_prev 1
  - max( 기존max_num, new_max_num )
- 다른 문자면 그냥 1로 바꿈
  - 그냥 1로 바꿈
프루트포스로 한칸씩 이동하며 y, x != ny, nx일 경우에만 swap 수행
- swap발생 시 A함수 둘 다 호출해서 수행
  - 끝나면 다시 원래대로 돌리기 위한 swap

시간복잡도

O(n^4)이지 않을까? -> 브루트포스라 장난아닐듯

필요 변수

문자열을 담은 graph
max_num -> max(a, b)활용해서 새롭게 업데이트

def row_check(n, graph, visit, max_num):
    # y++하며 가로 최대값 체크
    for y in range(n):
        for x in range(1, n):
            # 같으면
            if graph[y][x-1] == graph[y][x]:
                visit[y][x] = visit[y][x-1] + 1
                max_num = max(visit[y][x], max_num)
            else:
                visit[y][x] = 1
    return max_num

def column_check(n, graph, visit, max_num):
    # x++하며 세로 최대값 체크
    for x in range(n):
        for y in range(1, n):
            # 같으면
            if graph[y-1][x] == graph[y][x]:
                visit[y][x] = visit[y-1][x] + 1
                max_num = max(visit[y][x], max_num)
            else:
                visit[y][x] = 1
    return max_num
        
n = int(input())
graph = [list(input()) for _ in range(n)]
max_num = 0           

# 스왑 한번 할 때마다 위 함수 매번 수행하면 될듯
for y in range(n):
    for x in range(1, n):
        # 다르면
        if graph[y][x-1] != graph[y][x]:
            graph[y][x-1], graph[y][x] = graph[y][x], graph[y][x-1]
            
            visit = [[0]*n for _ in range(n)]    # (주의) 이렇게 만들어줘야함
            for i in range(n):    visit[i][0] = 1
            max_num = row_check(n, graph, visit, max_num)
            
            visit = [[0]*n for _ in range(n)]    # (주의) 이렇게 만들어줘야함
            visit[0] = [1]*n
            max_num = column_check(n, graph, visit, max_num)
            
            graph[y][x-1], graph[y][x] = graph[y][x], graph[y][x-1]

for x in range(n):
    for y in range(1, n):
        # 다르면
        if graph[y-1][x] != graph[y][x]:  
            graph[y-1][x], graph[y][x] = graph[y][x], graph[y-1][x]
            
            visit = [[0]*n for _ in range(n)]    # (주의) 이렇게 만들어줘야함
            for i in range(n):    visit[i][0] = 1
            max_num = row_check(n, graph, visit, max_num)
            
            visit = [[0]*n for _ in range(n)]    # (주의) 이렇게 만들어줘야함
            visit[0] = [1]*n
            max_num = column_check(n, graph, visit, max_num)
            
            graph[y-1][x], graph[y][x] = graph[y][x], graph[y-1][x]
        
print(max_num)