백준 3085 : 사탕 게임

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

3085번: 사탕 게임

https://github.com/HPYoo/swcodingtest/commit/b2639f755b1bae47517f022405bf6fde5b9f8721

sw coding 3085 update(Baekjoon) · HPYoo/swcodingtest@b2639f7

단순 구현 문제
 

1. 바꿀 수 있는 사탕 위치 확인하기

 쉽게 생각했다. 바꿀 수 있는 사탕의 위치 정보를 가지고 있으면 하나씩 바꿔가면서 카운트를 할 수 있을테니까 교환 가능한 사탕의 조합을 찾는 함수를 만들어 사용하면 편리할 것 같았다. 중복되는 정보를 피하기 위해 탐색 시작 위치는 방문처리를 해줘서 한번 결정한 조합은 두 번 카운트 되지 않도록 하였다.
 

temp = []
visited = [[False for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        visited[i][j] = True
        for k in range(4):
            nx = i + dx[k]
            ny = j + dy[k]
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] :
                if arr[i][j] != arr[nx][ny] :
                    temp.append([[i, j], [nx, ny]])

2. 사탕 세는 법

 집중안하면 가끔 헷갈릴때가 있다. 여기서 잔실수하지 않도록 하자
 -1) 행 / 열 중 하나를 선택하고 그걸 기본 캔디로 설정, 사탕개수 1개로 초기화
 -2) 그 다음 사탕과 비교
 -3) 같을 경우 사탕개수 카운트
 -4) 다를 경우 사탕개수는 1로 초기화 및 기본 캔디 변경
 -5) 모든 행 / 열에 대하여 조사
 아래는 행을 기준으로 사탕개수 세는 샘플 코드, 열을 기준으로 세는 경우도 동일

for i in range(N):
    max_candy = 1
    char = arr[i][0]
    for j in range(1, N):
        if char != arr[i][j] :
            max_candy = 1
            char = arr[i][j]
        else :
            max_candy += 1
        maxValue = max(maxValue, max_candy)

3. 전체코드
메모리 : 117104 KB, 시간 : 416 ms

N = int(input())
board = [list(map(str, input())) for _ in range(N)]

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

def find_combination(arr):
    temp = []
    visited = [[False for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            visited[i][j] = True
            for k in range(4):
                nx = i + dx[k]
                ny = j + dy[k]
                if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] :
                    if arr[i][j] != arr[nx][ny] :
                        temp.append([[i, j], [nx, ny]])
    return temp

def countcandy(arr, combination):
    x1, y1 = combination[0]
    x2, y2 = combination[1]
    # Change each other
    arr[x1][y1], arr[x2][y2] = arr[x2][y2], arr[x1][y1]
    # Count Candy : 'C', 'P', 'Z', 'Y'
    # 행 기준으로 파악
    maxValue = 0
    for i in range(N):
        max_candy = 1
        char = arr[i][0]
        for j in range(1, N):
            if char != arr[i][j] :
                max_candy = 1
                char = arr[i][j]
            else :
                max_candy += 1
            maxValue = max(maxValue, max_candy)
    # 열 기준으로 파악
    for j in range(N):
        max_candy = 1
        char = arr[0][j]
        for i in range(1, N):
            if char != arr[i][j] :
                max_candy = 1
                char = arr[i][j]
            else :
                max_candy += 1
            maxValue = max(maxValue, max_candy)
    arr[x1][y1], arr[x2][y2] = arr[x2][y2], arr[x1][y1]
    return maxValue

comb = find_combination(board)

result = 0
for features in range(len(comb)):
    cnt = countcandy(board, comb[features])
    result = max(result, cnt)

print(result)