2. 이맛에 푼다 Brute Force (백준 3085 파이썬) feat. 반례

사실 3085번 내 풀이가 브루트포스 방식이 맞는지에 약간 확신은 없지만, 일단 백준 분류에서 브루트포스로 뜨기 때문에 그렇게 적었다.

알고리즘을 놓은지 어연 6개월..(사실 6개월 훨씬 넘은듯) 정말 흐릿해진 기억 저편에 남은 delta값 사용 방식을 가지고 혼자 이렇게 저렇게 몇시간을 시도한 끝에, 기대하지 않은 '맞았습니다!!' 를 보는 희열은 참.. 행복하네.. 2시간 넘게 걸렸지만 역시 이게 맛이구나 하는 생각이 든다. 정말 자신감 바닥이었는데 혼자 오래걸려도 해결하고 나니 다시 자신감 뿜뿜 의욕 뿜뿜 열심히 준비해서 꼭 패스하고 싶ㄷㅏ

물론 정말 잘 푼 사람들이 많겠지만 일단 성공했으니 또 적어본다.

2시간 넘게 걸렸네..

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

3085번: 사탕 게임

문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

---

일단 접근으로는 한 칸씩 주변과 비교해서 같을 경우 쭉 가고, 다르면 바꿔서 최대값 저장하고, 넘어가기로 했다.

• 델타 값으로 탐색하며 주변과 비교하기 + 다를 경우 걔도 또 주변과 비교하기(바꾸기 위해)
• 한번은 바꿀 수 있어서 flag 값으로 주었다.

import sys
sys.stdin = open('3085.txt')

N = int(sys.stdin.readline())
board = [list(sys.stdin.readline().strip()) for _ in range(N)]

# 상우하좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

my_max = 1
for i in range(N):
    for j in range(N):
        
        # 보드 내 4방향 탐색
        for k in range(4):
            next_x = i+dx[k]
            next_y = j+dy[k]

            temp_max = 1
            flag = False
            # 맨 끝이 아닌 한에서
            while 0 <= next_x < N and 0 <= next_y < N:
                # 인접한 애와 같다면 그 방향 계속 탐색
                if board[i][j] == board[next_x][next_y]:
                    next_x += dx[k]
                    next_y += dy[k]
                    temp_max += 1
                else:
                    # 인접한 애와 다를 경우
                    if flag == False:
                        # 방향에 따라 우선순위 차이
                        if k == 1 or k == 3: 
                            # 가로로 가고있었으면 상하+가고있던방향
                            tx = [-1, 1, dx[k]]
                            ty = [0, 0, dy[k]]
                        else:
                            # 세로로 가고있었으면 좌우+가고있던방향
                            tx = [0, 0, dx[k]]
                            ty = [-1, 1, dy[k]]

                        for l in range(3):                            
                            check_x = next_x + tx[l]
                            check_y = next_y + ty[l]
                            if 0 <= check_x < N and 0 <= check_y < N:
                                #근방과 바꿔서 같아진다면 계속(1회만)
                                if board[i][j] == board[check_x][check_y]:
                                    if l == 0 or l == 1:
                                        flag = True
                                        temp_max += 1
                                        next_x += dx[k]
                                        next_y += dy[k]
                                        break
                                    # 가던 방향으로 바꾸면 한번만 바꾸고 종료
                                    else:
                                        temp_max += 1
                        # 주변에 바꿀게 없으면 종료
                        else:
                            break
                    # 이미 한번 바꾼거면 종료
                    else:
                        break
            
            # 전체 최대값 경신
            if my_max < temp_max:
                my_max = temp_max
        
print(my_max)

 

이렇게 완성한 부분을 뼈대로 시행착오를 많이 거쳤고, 특히 어떤 분께서 올려주신 테스트케이스로 정말 수정을 많이 했는데 (안 좋은 방법인 걸 알지만 엣지 케이스를 스스로 생각해 낼수가 없다 ^^) 놓친 부분들은 아래와 같으니 참고하시길..

• 왜인지 효율적으로 하고 싶어서 오른쪽으로, 아래로만 돌아도 다 확인이 되지 않을까? 라고 생각해서 dx, dy를 우, 하 로만 세팅했었다. - 물론 아님
• 인접한 애랑 바꾸고 나서 끝이 아니라, 바꾸고 나서 그 다음으로도 계속 탐색을 이어가야 함 - 그러다 또 다른 애를 마주치면 그때는 진짜 끝
• 바꾸는 과정이 우선순위가 다름. 가로로 가고 있엇으면 위 아래부터, 세로로 가고 있었으면 좌우부터 확인해야 하고, 가던 방향으로 바꿨으면 바로 종료.
• 나는 for else 문을 쓰기 위해 가던 방향 종료 시에는 break를 안거는 방법으로 구현함
• for문 while문 if문이 많아서 break와 else 처리에서 빠트린 부분이 종종 있어서 디버깅이 오래걸렸다..