백준 3085 사탕 게임

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

1차 구현

해당 문제는 최대 입력의 수가 50으로 제한이 되어 있기에, 브루투 포스 알고리즘을 계산을 해도 충분히 시간에 부족함 없이 해결할 수 있다고 판단되어 코드를 구현하였습니다.

처음에는 먼저 주어진 사탕 위치에서 최대를 먹을 수 있는 경우를 구해주었습니다.

그 다음은 행을 한 칸씩 변경해주고, 그 다음으로는 열을 한 칸씩 변경해주는 것으로 코드를 구현해주었습니다.

주의할 점은 중간에 입력된 N의 크기에 먹을 사탕의 수가 일치하면 거기서 종료할 수 있도록 해주는 것입니다.

import sys
input = sys.stdin.readline

boardSize = int(input())

row = [[] for i in range(boardSize)] # 열(세로) 부분 리스트
col = [[] for i in range(boardSize)] # 행(가로) 부분 리스트

for i in range(boardSize):
    color = input()
    for j in range(boardSize):
        col[i].append(color[j])
        row[j].append(color[j])

eatting = 0

colMax = 0
rowMax = 0
# 초기 보드에서 먹을 수 있는 사탕의 개수 세기
for i in range(boardSize):
    colMax = max(colMax,col[i].count("P"),col[i].count("Y"),col[i].count("Z"),col[i].count("C"))
    rowMax = max(rowMax,row[i].count("P"),row[i].count("Y"),row[i].count("Z"),row[i].count("C"))

eatting = max(rowMax,colMax)
if eatting == boardSize:
    print(boardSize)
else:
    colMax = 0
    rowMax = 0
    for i in range(boardSize):
        for j in range(boardSize-1):
            if col[i][j] != col[i][j+1]:
                col[i][j],col[i][j+1] = col[i][j+1],col[i][j]
                row[j][i],row[j+1][i] = row[j+1][i],row[j][i]
                colMax = max(colMax,col[i].count("P"),col[i].count("Y"),col[i].count("Z"),col[i].count("C"))
                rowMax = max(rowMax,row[j].count("P"),row[j].count("Y"),row[j].count("Z"),row[j].count("C"),row[j+1].count("P"),row[j+1].count("Y"),row[j+1].count("Z"),row[j+1].count("C"))
    eatting = max(rowMax,colMax,eatting)
    if eatting == boardSize:
        print(eatting)
    else:
        colMax = 0
        rowMax = 0
        for i in range(boardSize):
            for j in range(boardSize-1):
                if row[i][j] != row[i][j+1]:
                    row[i][j],row[i][j+1] = row[i][j+1],row[i][j]
                    col[j][i],col[j+1][i] = col[j+1][i],col[j][i]
                    rowMax = max(rowMax,row[i].count("P"),row[i].count("Y"),row[i].count("Z"),row[i].count("C"))
                    colMax = max(colMax,col[j].count("P"),col[j].count("Y"),col[j].count("Z"),col[j].count("C"),col[j+1].count("P"),col[j+1].count("Y"),col[j+1].count("Z"),col[j+1].count("C"))
        eatting = max(rowMax,colMax,eatting)
        print(eatting)

그러나 결과는 안타깝게도 틀렸습니다.

아무리 봐도 틀린것이 없다고 판단되어 다음 날 문제를 다시 보고 풀어보았는데, 코드가 완전히 잘못되었음을 인지할 수 있었습니다.
위의 코드는 같은 색의 사탕이 인접한 경우를 카운트 하는 것이 아니라 단순히 해당 열이나 행에 있는 색의 수를 세도록 구현하였던 것입니다.
왜 그랬는지 정말 의아했습니다 🤦‍♀️

2차 구현

2차 구현은 위에서 발견한 문제를 인지하여 수정하였고, 추가로 반복적인 동작은 함수로 코드를 정리하면서 구현하였습니다.

추가로 주의할 점은, 리스트를 복사할 때, = 을 사용하면 주소가 복사되므로 값을 변경시 원본에도 영향을 주는 것을 고려해서, 원본을 유지하고자할 때는 .copy() 함수를 써야 한다는 점 입니다.

import sys
input = sys.stdin.readline

boardSize = int(input())

row = [[] for i in range(boardSize)] # 열(세로) 부분 리스트
col = [[] for i in range(boardSize)] # 행(가로) 부분 리스트

for i in range(boardSize):
    color = input()
    for j in range(boardSize):
        col[i].append(color[j])
        row[j].append(color[j])

# 중복된 부분을 카운트 해주는 함수 -> 해당 동작을 반복 수행해야 될 것 같기에 함수로 구현
def countCandy(sample):
    global boardSize
    temp = 1
    multiCandy = 1
    for i in range(boardSize-1):
        if sample[i] == sample[i+1]:
            temp +=1
            multiCandy = max(multiCandy,temp)
        else:
            temp = 1
    return multiCandy

eatting = 0

colMax = 1
rowMax = 1

# 초기 보드에서 먹을 수 있는 사탕의 개수 세기
for i in range(boardSize):
    colMax = max(colMax,countCandy(col[i]))
    rowMax = max(rowMax,countCandy(row[i]))

eatting = max(rowMax,colMax)

# 한 칸씩 변경하면서 경우의 수를 따져주기
if eatting != boardSize:
    colMax = 0
    rowMax = 0
    # 먼저 행을 한 칸씩 먼저 변경
    for i in range(boardSize):
        for j in range(boardSize-1):
            # copy() 함수를 사용해서 주소가 아닌 새 객체를 생성하여 복사
            rowtempBefore = row[j].copy()
            rowtempAfter = row[j+1].copy()
            coltemp = col[i].copy()

            if col[i][j] != col[i][j+1]:
                coltemp[j],coltemp[j+1] = coltemp[j+1],coltemp[j]
                rowtempBefore[i],rowtempAfter[i] = rowtempAfter[i],rowtempBefore[i]
                colMax = max(colMax, countCandy(coltemp))
                rowMax = max(rowMax, countCandy(rowtempAfter),countCandy(rowtempBefore))
    eatting = max(rowMax,colMax,eatting)

    # 마지막으로 열을 한 칸씩 변경
    if eatting != boardSize:
        colMax = 0
        rowMax = 0
        for i in range(boardSize):
            for j in range(boardSize-1):
                # copy() 함수를 사용해서 주소가 아닌 새 객체를 생성하여 복사
                rowtemp = row[i].copy()
                coltempBefore = col[j].copy()
                coltempAfter = col[j+1].copy()
                if row[i][j] != row[i][j+1]:
                    rowtemp[j],rowtemp[j+1] = rowtemp[j+1],rowtemp[j]
                    coltempBefore[i],coltempAfter[i] = coltempAfter[i],coltempBefore[i]
                    rowMax = max(rowMax,countCandy(rowtemp))
                    colMax = max(colMax, countCandy(coltempBefore), countCandy(coltempAfter))
        eatting = max(rowMax,colMax,eatting)
print(eatting)

결과는 드디어 정답을 얻을 수 있었습니다. 😚