백준 3085번 - BOMBONI

한시온·2022년 3월 3일
0
post-thumbnail

해설

접근 방식

  1. 같은 행 또는 열에서 인접한 두 요소의 위치를 swap한다.
  2. swap 했을 때의 보드에서 같은 색의 사탕이 연속하는 최댓값을 구한다.
  3. swap한 두 요소를 재swap하여 초기 보드로 복귀한다.
    (1번으로 가서 반복)

count = 1 초기화를 하는 이유?

check() 함수를 보면 인접한 두 요소를 비교하고 같지 않은 경우 count = 1로 값을 초기화하는 것을 알 수 있다. 언뜻 보면 해당 코드는 불필요해 보인다. 예를 들어 AAB 행에서 AA를 비교할 때 count == 2가 되지만 그 다음에 AB를 비교할 때 같지 않으므로 count == 1이 되고 이는 논리적으로 납득이 어렵다. (내가 그랬다) count는 같은 행 또는 열에서 같은 색의 사탕이 연속한 개수이기 때문이다.

...
  # row
    for _i in range(n):
        _count = 1
        for _j in range(n - 1):
            if candy[_i][_j] == candy[_i][_j + 1]:
                _count += 1
                max_ = max(max_, _count)
            else:
                _count = 1 # here
                ...

그러나 해당 로직이 없다면 문제가 발생할 수 있다.
AABB행의 경우를 생각해보자.

1. `AA` 비교 -> 두 요소가 같으므로 count == 2 (+1)
2. `AB` 비교 -> 두 요소가 다르므로 count == 2
3. `BB` 비교 -> 두 요소가 같으므로 count == 3 (+1)

같은 색의 사탕이 연속한 개수는 2임에도 3이라는 엉뚱한 값이 나온다. 만약 초기화하는 로직이 있다면 AABB행은 다음과 같이 처리될 것이다.

1. `AA` 비교 -> 두 요소가 같으므로 count == 2 (+1)
2. `AB` 비교 -> 두 요소가 다르므로 count == 1
3. `BB` 비교 -> 두 요소가 같으므로 count == 2 (+1)

그렇다면 AAB행에서 count == 1이 되는 문제는 어떻게 할 것인가?
이는 인접한 두 요소가 같을 때마다 count의 값을 증감한 뒤 기존의 최댓값과 비교하고 더 큰 값을 대입함으로써 해결할 수 있다.

...
  # row
    for _i in range(n):
        _count = 1
        for _j in range(n - 1):
            if candy[_i][_j] == candy[_i][_j + 1]:
                _count += 1
                max_ = max(max_, _count) # here
            else:
                _count = 1
                ...

AAB 행의 경우를 생각해보자. count의 값이 1이 되어도 같은 값이 연속한 개수의 최댓값을 _max 변수에 이미 저장했고 그 값을 입력값의 결과로서 출력하므로 문제가 해결된다.

1. `AA` 비교 -> 두 요소가 같으므로 count == 2 (+1)
2. 최댓값 비교 -> max_ < count 이므로 max_ = count (max_ == 2)
3. 'AB' 비교 -> 두 요소가 다르므로 count == 1

풀이

def check():
    global max_

    # row
    for _i in range(n):
        _count = 1
        for _j in range(n - 1):
            if candy[_i][_j] == candy[_i][_j + 1]:
                _count += 1
                max_ = max(max_, _count)
            else:
                _count = 1

    # column
    for _i in range(n):
        _count = 1
        for _j in range(n - 1):
            if candy[_j][_i] == candy[_j + 1][_i]:
                _count += 1
                max_ = max(max_, _count)
            else:
                _count = 1


max_ = 0
n = int(input())
candy = [list(input()) for _ in range(n)]

# row
for i in range(n):
    for j in range(n - 1):
        if candy[i][j] == candy[i][j + 1]:
            continue
        else:
            candy[i][j], candy[i][j + 1] = candy[i][j + 1], candy[i][j]
            check()
            candy[i][j + 1], candy[i][j] = candy[i][j], candy[i][j + 1]

# column
for i in range(n):
    for j in range(n - 1):
        if candy[j][i] == candy[j + 1][i]:
            continue
        else:
            candy[j][i], candy[j + 1][i] = candy[j + 1][i], candy[j][i]
            check()
            candy[j + 1][i], candy[j][i] = candy[j][i], candy[j + 1][i]

print(max_)
profile
가볍고 무겁게

0개의 댓글