BJ2652 블록맞추기

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

풀이

알고리즘 : DFS & 블록 체크 구현

Pseudo-Code

1. 왼쪽 위 첫 점(1,1) 부터 오른쪽 아래(16,16) 마지막 점 까지 탐색한다.

2. 'ㄷ'자 블록(1)을 만나면 DFS를 해서 1인 지점을 모두 check배열에서 True로 체크하고 왼쪽 맨 윗 점 P1과 오른쪽 맨 아래 점 P2을 만든다.

3. P1(y1,x1)와 P2(y2,x2)로 만들어지는 사각형에서 뚫려있는 변의 원래길이 뚫린 길이와 변의 위치(상0 우1 하2 좌3)를 찾는다.

4. 해당변의 시작부터 'ㅗ'자 모양의 블록을 끼워서 직사각형이 되는지 아닌지 체크한다.

   1. 뚫려있는 변의 길이와 u를 비교하고, 뚫린 길이와 y를 비교하여 다르다면 불가능

   2. 4-1이 가능하다면 'ㅗ'자 모양에 맞게 색칠한다. 색칠하려는 칸이 1일 경우 불가능.

      • 뚫린 변의 위치가 상 일때

        (y1-v, x2-u+1) ~ (y1-1, x2)

        (y1, x2-w-y+1) ~ (y1+x-1, x2-w)

      • 뚫린 변의 위치가 우 일때

        (y2-u+1, x2+1) ~ (y2, x2+v)

        (y2-w-y+1,x2-x+1) ~ (y2-w, x2)

      • 뚫린 변의 위치가 하 일때

        (y2+1, x1) ~ (y2+v, x1+u-1)

        (y2-x+1, x1+w) ~ (y2,x1+w+y-1)

      • 뚫린 변의 위치가 좌 일때

        (y1, x1-v) ~ (y1+u-1, x1-1)

        (y1+w, x1) ~ (y1+w+y-1, x1+x-1)

Code

#! 2020.02.25
# TODO BJ2652블록맞추기
N = int(input())
U, V, W, X, Y = map(int,input().split())
SIZE = U*V + X*Y
inMap = [list(map(int,input().split())) for _ in range(N)]
visited = [[False for _ in range(N)] for _ in range(N)]
result = []
dx = [1,0,-1,0]
dy = [0,1,0,-1]

def inRange(yy,xx):
    if yy>=0 and xx>=0 and yy<N and xx<N:
        return True
    else:
        return False

def DFS(yy,xx):
    maxX = xx
    maxY = yy
    for dir in range(4):
        nextY = yy+dy[dir]
        nextX = xx+dx[dir]
        if inRange(nextY,nextX) and not visited[nextY][nextX] and inMap[nextY][nextX]==1:
            visited[nextY][nextX] = True
            tmpY,tmpX = DFS(nextY,nextX)
            if tmpY>=maxY and tmpX>=maxX:
                maxX,maxY = tmpX,tmpY 
    return maxY,maxX

def cntBlock(startY,startX,endY,endX,val):
    cnt = 0
    for i in range(startY,endY+1):
        for j in range(startX,endX+1):
            if inRange(i,j) and inMap[i][j]==val:
                cnt += 1
    return cnt

def checkBlock(yy1,xx1,yy2,xx2):
    n0 = cntBlock(yy1,xx1,yy1,xx2,1) #up
    n1 = cntBlock(yy1,xx2,yy2,xx2,1) #right
    n2 = cntBlock(yy2,xx1,yy2,xx2,1) #down
    n3 = cntBlock(yy1,xx1,yy2,xx1,1) #left
    side = -1       # 0 : up, 1 : right, 2 : down, 3 : left
    blank = 0
    length = 0
    if n1==n3:
        if n0>n2:
            side = 2
            blank = n0-n2
            length = n0
        else:
            side = 0
            blank = n2-n0
            length = n2
    else:
        if n1>n3:
            side = 3
            blank = n1-n3
            length = n1
        else:
            side = 1
            blank = n3-n1
            length = n3

    if length == U and blank == Y and cntBlock(yy1,xx1,yy2,xx2,0) == X*Y:
        cntEmpty = 0
        if side == 0:
            cntEmpty += cntBlock(yy1,xx2-W-Y+1,yy1+X-1,xx2-W,0)
            cntEmpty += cntBlock(yy1-V,xx2-U+1,yy1-1,xx2,0)
        elif side == 1:
            cntEmpty += cntBlock(yy2-W-Y+1,xx2-X+1,yy2-W,xx2,0)
            cntEmpty += cntBlock(yy2-U+1,xx2+1,yy2,xx2+V,0)
        elif side == 2:
            cntEmpty += cntBlock(yy2-X+1,xx1+W,yy2,xx1+W+Y-1,0)
            cntEmpty += cntBlock(yy2+1,xx1,yy2+V,xx1+U-1,0)
        else:
            cntEmpty += cntBlock(yy1+W,xx1,yy1+W+Y-1,xx1+X-1,0)
            cntEmpty += cntBlock(yy1,xx1-V,yy1+U-1,xx1-1,0)
        if cntEmpty==SIZE:
            return True
    return False

def getResult():
    for y1 in range(N):
        for x1 in range(N):
            if not visited[y1][x1] and inMap[y1][x1]==1:
                visited[y1][x1] = True
                y2,x2 = DFS(y1,x1)
                if checkBlock(y1,x1,y2,x2):
                    tmpRet = [0]*2
                    tmpRet[0],tmpRet[1] = y1+1,x1+1
                    result.append(tmpRet)

getResult()
print(len(result))
for ret in result:
    print(*ret)

실수

1. 'ㅗ' 채웠을 때 모두다 채워진 직사각형이어야 했다.

   내가 했던 방식에서는 빈공간이 생겨도 'ㅗ'가 들어가는데에는 문제가 없기 때문에 오류가 생겼었다.

2. 채울 수 있는 직사각형이 몇갠지만 찾는거지 동시에 채워야하는건 아니다.

   내가 했던 방식에서는 채우는 코드를 작성해서 가능한 경우에는 채우고 넘어가도록 구현했었지만 문제 조건에 그런 조건은 없었다.