상어중학교 (골드2) -삼성기출

문제

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

내풀이

n,m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
dy = [0,1,0,-1]
dx = [1,0,-1,0]
answer = 0   #최종 점수

def rotate(arr):  ## 반시계 90도 회전
    temp = [arr[i][:] for i in range(len(arr))]

    for i in range(len(arr)):
        for j in range(len(arr[0])):
            arr[len(arr)-1-j][i] = temp[i][j]


def down(arr):  ## 중력작용 밑으로 내리
    temp = [arr[i][:] for i in range(len(arr))]

    for i in range(len(arr)-2,-1,-1):
        for j in range(len(arr[0])):
            if arr[i][j] == -1 or arr[i][j] == -2: continue
            row = i
            for k in range(i+1,len(arr)):
                if arr[k][j] != -2: break
                row = k

            if row != i: # 내리는 상황일경우
                arr[row][j] = arr[i][j]
                arr[i][j] = -2


def dfs(arr,y,x,target):   # 좌표모음, 무지개수, 기준블록 좌표
    q = []
    result = []
    q.append((y,x))
    result.append((y,x))
    focus = (-1,-1)

    visited[y][x] = True
    rainbow = 0
    while(q):
        a,b = q.pop()
        for i in range(4):
            ny, nx = a + dy[i], b + dx[i]
            if 0 <= ny < n and 0 <= nx < n and visited[ny][nx] == False \
                    and (arr[ny][nx] == target or arr[ny][nx] == 0):
                q.append((ny,nx))
                result.append((ny,nx))
                visited[ny][nx] = True
                rainbow += 1 if arr[ny][nx] == 0 else 0   # 무지개수 체

    result.sort(key = lambda x:(x[0],x[1]))
    for a,b in result:   # 기준블록 탐색
        if arr[a][b] == 0: continue
        focus = (a,b)
        break


    return [result,rainbow,focus]


def reset_rainbow(arr):
    for i in range(len(arr)):
        for j in range(len(arr[0])):
            if arr[i][j] == 0:
                visited[i][j] = False

def reset_visited():
    for i in range(len(arr)):
        for j in range(len(arr[0])):
            visited[i][j] = False



def find_max_group(arr):
    max_list = []
    global answer
    for i in range(len(arr)):
        for j in range(len(arr[0])):
            if arr[i][j]>=1 and visited[i][j] == False: ## 아직 방문한적 없는 일반블록이면 dfs
                temp = dfs(arr,i,j,arr[i][j])
                if len(temp[0]) >=2:
                    max_list.append(temp)  ## 블록개수 2개이상이면 추
                reset_rainbow(arr)

    max_list.sort(key=lambda x:(-len(x[0]),-x[1],-x[2][0],-x[2][1])) # 개수, 무지개수, 행, 열 큰 순으로 정렬
    if not max_list:
        return False

    else :
        for y,x in max_list[0][0]:
            arr[y][x] = -2
        answer += len(max_list[0][0]) ** 2
        return True

def end_check(arr):
    flag= True

    for i in range(len(arr)):
        for j in range(len(arr[0])):
            if arr[i][j] != -2:
                return True

    if flag:
        return False

while(1):
    reset_visited() ## dfs 반복을 위해 초기화
    if not find_max_group(arr):  ## 탐색된 블록그룹 없으면 종료
        break
    down(arr)
    rotate(arr)
    down(arr)

print(answer)

주의점

하면서 틀려가지고 시간썼던부분들만 정리해보았다.

한번 돌릴때마다 visited 초기화 해줘야 하는거 잊지말자
중력에 블록 내릴때 빈블록이면 패스하게끔 하는거,

종료조건이 전부다 사라지는게 아니라 새로운 그룹이 만들어지지 않을때인거 실수안하게 조심

끝!