3805번 문제풀이 : 완전탐색 알고리즘 (시뮬레이션)

1. 문제 분석

한 문장 요약

N * N 크기의 사탕 보드에서 인접한 사탕을 교환하여 (캔디 크러쉬처럼) 가장 긴 연속된 색 사탕 개수를 찾는 문제

입출력 정리

입력

• 보드 크기 N
• N x N 크기의 사탕 배치

출력

• 한 번의 교환으로 만들 수 있는 최대 연속된 같은 색 사탕 개수

필요한 알고리즘

• 완전탐색 → 시뮬레이션 (교환 후 원상복구 필요)

---

2. 의사코드

1. N 입력받기
2. N x N 크기의 보드 입력받기
3. 최대 연속된 사탕 개수를 구하는 함수 작성:
   • 행, 열을 순회하면서 같은 색이 연속된 개수를 계산
4. 모든 위치 (i, j)에 대해:
   1. 오른쪽 교환: j+1이 범위 안에 있으면, board[i][j] <-> board[i][j+1] 교환
      • 최대 연속된 사탕 개수 계산
      • 원래 상태로 복구
   2. 아래쪽 교환: i+1이 범위 안에 있으면, board[i][j] <-> board[i+1][j] 교환
      • 최대 연속된 사탕 개수 계산
      • 원래 상태로 복구
5. 최댓값 출력

---

3. 코드 풀이

#(의사코드 3) 최대 연속된 사탕 개수를 구하는 메소드
def max_candy_count(board, N) :
    max_count = 1

    for i in range(N):
        row_count = 1
        col_count = 1 
        #가로 연속 개수 확인 
        for j in range(1, N): # 0 < j < N
            if board[i][j] == board[i][j - 1]: # 이전꺼랑 같은 게 아니면 개수 세기
                row_count += 1 
            else : 
                max_count = max(max_count, row_count)
                row_count = 1 #초기화 

            #세로 연속 개수 확인
            if board[j][i] == board[j - 1][i]:
                col_count += 1
            else:
                max_count = max(max_count, col_count)
                col_count = 1#초기화 
        
        # for문 종료 후 가장 큰 것 
        max_count = max(max_count, row_count, col_count)

    return max_count

# (의사코드 4)모든 사탕을 교환하는 완전탐색
def solve_candy_game(N, board):
    max_candies = 0

    for i in range(N):
        for j in range(N):
            #오른쪽  사탕이 있다면
            if j + 1 < N:
                board[i][j], board[i][j + 1] = board[i][j + 1], board[i][j]
                max_candies = max(max_candies, max_candy_count(board, N))
                #원상복귀
                board[i][j], board[i][j + 1] = board[i][j + 1], board[i][j] 

            #아래 사탕이 있다면 
            if i + 1 < N:
                # 교환
                board[i][j], board[i + 1][j] = board[i + 1][j], board[i][j]
                max_candies = max(max_candies, max_candy_count(board, N)) 
                # 원래대로 복구 
                board[i][j], board[i + 1][j] = board[i + 1][j], board[i][j] 
    return max_candies

---

4. 문제 핵심

시뮬레이션 & 완전탐색

• 의사코드 작성의 중요성
• 완전탐색이 필요한 경우
  1. N의 범위가 크지 않을 때 → 크다면 다른 방법 필요
  2. 전체 경우의 수를 고려해야 할 때 → 완전탐색 적용 가능

추가 개념 정리

• 2차원 배열 순회 → 이중 for문 활용
• 리스트는 str(iterable 객체) 넣으면 알파벳 단위로 저장

s = "hello"
print(list(s))  # ['h', 'e', 'l', 'l', 'o']