Baekjoon3085-사탕게임

백준 사이트 3085 - 사탕게임 문제입니다.

☑️ 1. 문제

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

---

☑️ 2. Input , Output

---

☑️ 3. 분류 및 난이도

코딩테스트 준비 - 기초 문제입니다.

---

☑️ 4. 생각한 것들

• 이 문제가 차라리 모든 경우의 수(단 한 번만 바꾸는 것이 아닌)것 같은 거였으면 더 어려웠을텐데 그러지는 않아서 실버3으로 책정된 문제라 생각했습니다.
• 그래도 탐색은 해줘야하고, 세로와 가로를 따로따로 해줘야했어서 이를 분리해서 하였습니다.
• 지나고 와서 생각해보면 반복되는 구문을 줄여서 좀 더 이쁘게 짤 수 있지만 알고리즘 문제에 그런 노고를 쓰지는 않고 싶습니다..

---

5. code

# 오후 10시 37분
import copy
import sys
from collections import deque

n = int(sys.stdin.readline())
map = [[0 for col in range(n)] for row in range(n)]

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

answer = 0


def BFS(map, x, y):
    v = [[False for col in range(n)] for row in range(n)]
    dq = deque()
    dq.append([x, y])
    v[x][y] = True
    result = 0
    count = 1
    while dq:
        i, j = dq.popleft()
        result = max(result, count)
        for k in range(0,4,2):
            newx, newy = i + dx[k], j + dy[k]
            if 0 <= newx < n and 0 <= newy < n and v[newx][newy] == False and map[x][y] == map[newx][newy]:
                count+=1
                dq.append((newx, newy))
                v[newx][newy] = True
    dq.append([x, y])
    result = max(result, count)
    count = 1
    while dq:
        i, j = dq.popleft()
        result = max(result, count)
        for k in range(1,4,2):
            newx, newy = i + dx[k], j + dy[k]
            if 0 <= newx < n and 0 <= newy < n and v[newx][newy] == False and map[x][y] == map[newx][newy]:
                count+=1
                dq.append((newx, newy))
                v[newx][newy] = True
    return result


def check_status(map, x, y):
    result = 0
    for i in range(4):
        tempmap = copy.deepcopy(map)
        newx = x + dx[i]
        newy = y + dy[i]
        if 0 <= newx < n and 0 <= newy < n and map[x][y] != map[newx][newy]:
            tempmap[x][y], tempmap[newx][newy] = tempmap[newx][newy], tempmap[x][y]
            result = max(result, BFS(tempmap, x, y))
    return result


for i in range(n):
    inputstr = input().split()
    for j in range(n):
        convert = inputstr[0][j:j + 1]
        map[i][j] = convert

for i in range(n):
    for j in range(n):
        answer = max(BFS(map, i, j), check_status(map, i, j), answer)

print(answer)

---

6. 후기

• 개선점으로는 세로, 가로로 나눠서 함수를 작성하기

c++로 작성이 필요하거나 도움이 필요하시면 댓글을 작성해주세요.!! 기록용이라 설명이 자세하지 않습니다.