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

RostoryT·2022년 6월 27일
0

Brute force

목록 보기
2/18


  • 캔디크러쉬같은 느낌인듯

  • 처음에 삽질을 너무 많이 했음

  • 어떻게 풀어야 할지, 처음 접하니까 감이 안와서 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)    

헐?

시간초과 날줄 알았는데 ㅋ


검색해보니

다른 블로그 솔루션도 다 나랑 똑같이 풀었음(함수는 두 가지 버전으로 하거나 하나로 합치거나!)

  • 브루트포스의 정석과도 같은 문제라고 한다
  • 반복문을 기본 4중첩씩 사용,
  • 사탕이 바꼈을 때 각각의 케이스를 조사해야 하므로
profile
Do My Best

0개의 댓글