BOJ14890-경사로-알고리즘 복습 3일차

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

문제 설명

board에 각 라인별로 경사로를 놓을수있는지 없는지 판별하는 문제다.

경사로의 높이는 1이다.

 

아이디어

각 라인별로 연속되는 숫자끼리 묶고 경사로의 크기대로 묶은 숫자들을 분할 시킨 후 규칙에 따라 덩어리를 제거하는 방식을 생각했다.

 

겪었던 문제

1. 테스트케이스에 맞춰 틀리는 케이스만 고치는 식으로 수정하다보니 정답처리받는데 많은 시간이 걸렸다.

2. 경사로의 길이가 1인 경우를 생각하지 못했다. 이미 경사로를 세운 땅의 연속된 길이를 1로 바꾸는 코드가 있었는데

중복으로 경사로가 세우지는 문제가 생겼다.

3. 조건문을 너무 복잡하게 만들었었다. 각 단계에서 한덩어리씩 지워나가면 됐는데 어떤경우는 두덩어리를 지우고 하니

조건식이 너무 복잡해졌었다.

 

 

풀이 코드

'''
아이디어
1. n*n개의 보드판에서 2n번 시행하면 됌.
2. 1행의 경사로를 판별한다면 1행에서 덩어리를 묶고 덩어리를 쪼개고 병합해나가는 과정 필요.
예시) L이 2이고 22223222222223 라는 길이 있다면
1단계(덩어리화). 2222 3 22222222 3
2단계(쪼개기). 22 22 3 2222 2222 3
3단계(쪼개기). 22 22 3 22 22 22 22 3
4단계(병합)
오른쪽에 같은 크기의 덩어리가 있다면 그 해당 차의 덩어리를 버림
다음것이 1 크다면 다음것만 남김.(리스트의 크기가 2라면 둘다 없앰)
다음것이 1 작으면 다음 덩어리의 크기를 봄. 그후 둘다없앰
22 22 3 22 22 22 22 3
22 3 22 22 22 22 3
3 22 22 22 22 3
22 22 22 3
22 22 3
22 3
'''

from collections import deque

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


def countRight(start):
    chunk = deque()
    chunk.append((board[start][0],1))
    for i in range(1, N):
        c = chunk.pop()
        if c[0] == board[start][i]:
            chunk.append((c[0],c[1]+1))
        else:
            chunk.append(c)
            chunk.append((board[start][i],1))
    return chunk

def countDown(start):
    chunk = deque()
    chunk.append((board[0][start],1))
    for i in range(1, N):
        c = chunk.pop()
        if c[0] == board[i][start]:
            chunk.append((c[0],c[1]+1))
        else:
            chunk.append(c)
            chunk.append((board[i][start],1))
    return chunk


def divide(L,chunk):
    newChunk = []
    while chunk:
        c = chunk.popleft()
        divideResult = c[1]//L
        if divideResult >= 1:
            for _ in range(c[1]//L):
                newChunk.append((c[0],L))
        else:
            newChunk.append((c[0],1))
    return newChunk

def union(L,chunk):
    if len(chunk) == 1:
        return True
    count = len(chunk)-1
    while True:
        if count <= 0:
            if len(chunk) == 1:
                return True
        if chunk[0][0]+1 == chunk[1][0]:
            if chunk[0][1] == L:
                    chunk.pop(0)
                    count-=1
            else:
                return False
        elif chunk[0][0] == chunk[1][0]+1:
            if chunk[1][1] == L:
                    chunk.pop(0)
                    newChunk = chunk.pop(0)
                    chunk.insert(0,(newChunk[0],0))
                    count-=1
            else:
                return False
        elif chunk[0][0] == chunk[1][0]:
                chunk.pop(0)
                count-=1
        else:
            return False

def simulation():
    result = 0
    for i in range(N):
        if union(L,divide(L,countRight(i))):
            result += 1
        if union(L,divide(L,countDown(i))):
            result += 1
    print(result)

simulation()

 

문제 난이도에 비해 많은 시간을 할애한것같아 접근법이 잘못됐다고 느꼈다.

문제를 다푼후 다른 사람의 풀이를 찾아봤다.

 

백준 14890 경사로 삼성 SW역량테스트 (Python)

 

해당 블로그 글의 접근법이 가장 마음에 들었다.

나는 연속되는 수를 덩어리 지어 풀려고 했는데 이 글의 경우 각 라인에 따라 경사로를 체크하는 리스트를 만들었고

라인의 왼쪽부터 직접 경사로가 필요하면 경사로를 추가하고 겹치거나 만들지못하면 예외처리하는 방식으로 코드를 작성했다.

연속된 수를 구하고 나누는 과정보다 직접 하나하나 체킹해나가는 접근방식이 더 쉬운것같은데 앞으로는

이러한 접근법도 염두해두어야겠다는 생각을 했다.