[python code review] 2주차 : (안전 영역, 자물쇠와 열쇠, 톱니바퀴)

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

2468번: 안전 영역

[안전 영역] (중) 

from collections import deque

n = int(input())
board = []
min_val, max_val = 100, 1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs(depth, i, j):
    # 0으로 방문처리 
    tmp[i][j] = 0
    q = deque([(i, j)])
    while q:
        x, y = q.popleft()
        for xx, yy in zip(dx, dy):
            nx = xx + x
            ny = yy + y
            if 0 <= nx < n and 0 <= ny < n:
                if tmp[nx][ny] > depth:
                    # 0으로 방문처리 
                    tmp[nx][ny] = 0
                    q.append((nx, ny))
    return 1


for _ in range(n):
    data = list(map(int, input().split()))
    board.append(data)
    min_val = min(min_val, min(data))
    max_val = max(max_val, max(data))

tmp = [[0]*n for _ in range(n)]
result = 1
count = 0
for target in range(min_val, max_val):
    for i in range(n):
        for j in range(n):
            tmp[i][j] = board[i][j]
    count = 0
    for i in range(n):
        for j in range(n):
            if tmp[i][j] > target:
                count += bfs(target, i, j)
    result = max(result, count)
print(result)

 

1. 메모리 초과난 코드 

dfs로 풀어보려 했더니 RecursionError 발생했다.

sys.setrecursionlimit을 사용해봤지만 그래도 메모리 초과가 발생하였다. 

import sys
sys.setrecursionlimit(15000)
n = int(input())
board = []
min_val, max_val = 100, 1
dx = [-1,0,1,0]
dy = [0,1,0,-1] 

def dfs(depth, x, y):
    tmp[x][y] = 0
    for xx, yy in zip(dx, dy):
        nx = xx + x
        ny = yy + y
        if 0 <= nx < n and 0 <= ny < n:
            if tmp[nx][ny] > depth:
                dfs(depth, nx, ny)
    return 1

for _ in range(n):
    data = list(map(int, input().split()))
    board.append(data)
    min_val = min(min_val, min(data))
    max_val = max(max_val, max(data))

tmp = [[0]*n for _ in range(n)]
result, count = 1, 0
for target in range(min_val, max_val):
    # 임시 테이블 초기화 
    for i in range(n):
        for j in range(n):
            tmp[i][j] = board[i][j]
    count = 0
    for i in range(n):
        for j in range(n):
            # target보다 큰 경우 카운트
            if tmp[i][j] > target:
                count += dfs(target, i, j)
    result = max(result, count)
print(result)

그런데.. 어떤 블로그 코드 리뷰를 보니 어이없게도 dx, dy 좌표를 

[-1,0,1,0]

[0,1,0,-1] 에서

[-1,1,0,0]

[0,0,-1,1] 으로 바꿔주는 것으로 문제를 해결할 수 있었다... 

 

 

https://programmers.co.kr/learn/courses/30/lessons/60059

코딩테스트 연습 - 자물쇠와 열쇠

[자물쇠와 열쇠] (중상)

def turnKey(key):
    m = len(key)
    # 90도 회전
    ret = [[0] * m for _ in range(m)]
    for r in range(m):
        for c in range(m):
            ret[c][m - 1 - r] = key[r][c]
    return ret


def check(board, M, N):
    for i in range(N):
        for j in range(N):
            if board[M + i][M + j] != 1:
                return False
    return True


def solution(key, lock):
    m = len(key)
    n = len(lock)
    bigLock = [[0] * (m * 2 + n) for _ in range(m * 2 + n)]
    # 자물쇠 중앙 배치
    for i in range(n):
        for j in range(n):
            bigLock[m + i][m + j] = lock[i][j]
    turned_key = key
    # 모든 방향 (4번 루프)
    for _ in range(4):
        turned_key = turnKey(turned_key)
        for i in range(1, m + n):
            for j in range(1, m + n):
                # 열쇠 넣기
                for r in range(m):
                    for c in range(m):
                        bigLock[i + r][j + c] += turned_key[r][c]
                # 열쇠로 자물쇠를 열 수 있는지 검사 
                if check(bigLock, m, n):
                    return True
                # 열쇠 빼기
                for r in range(m):
                    for c in range(m):
                        bigLock[i + r][j + c] -= turned_key[r][c]

    return False

 

2. 틀린 풀이

범위 설정에 있어서 에러가 발생하였다. 범위설정을 상하좌우로 m-1에서 m으로 변경해주었더니 잘 구현되었다.

(2022-02-18 수정) -> 범위설정을 잘못한 줄 알았더니 turn_key = turnKey(key) 이부분에서 실수를 한 것이었다.

for문 안에서 회전된 키는 전 타임에 회전한 키를 다시 90도 돌린 것이다. 따라서 for _ in range(4) 밖에서 먼저 turn_key = key로 초기화해주고 turn_key = turnKey(key)를 turn_key = turnKey(turn_key)로 수정해주면 정상 동작한다.  

def turnKey(key):
    m = len(key)
    # 90도 회전
    ret = [[0] * m for _ in range(m)]
    for r in range(m):
        for c in range(m):
            ret[c][m - 1 - r] = key[r][c]
    return ret

def checkBigLock(bigLock, m, n):
    for i in range(n):
        for j in range(n):
            if bigLock[i+m-1][j+m-1] != 1:
                return False
    return True

def solution(key, lock):
    m = len(key)
    n = len(lock)
    bigLock = [[0] * (n + 2 * m - 2) for _ in range((n + 2 * m - 2))]

    # 큰 자물쇠 세팅
    for i in range(n):
        for j in range(n):
            bigLock[i + m - 1][j + m - 1] = lock[i][j]
    # 키 회전시켜 보기
    for _ in range(4):
        turn_key = turnKey(key)
        # 큰 자물쇠에 turn_key 뿌리기
        for i in range(0, n+m-1):
            for j in range(0, n+m-1):
                for r in range(m):
                    for c in range(m):
                        bigLock[i + r][j + c] += turn_key[r][c]
                # 자물쇠가 맞지 않으면
                if not checkBigLock(bigLock, m, n):
                    # 큰 자물쇠 원상태로 되돌리기
                    for r in range(m):
                        for c in range(m):
                            bigLock[i + r][j + c] -= turn_key[r][c]
                # 자물쇠가 맞으면 true 리턴
                else:
                    return True
    return False

 

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

14891번: 톱니바퀴

[톱니바퀴] (중상)

chain = [input() for _ in range(4)]
k = int(input())

def turnLeft(s):
    data = s[1:] + s[0]
    return data

def turnRight(s):
    data = s[-1] + s[:-1]
    return data

def move(i, d):
    # 시계 방향
    if d == 1:
        chain[i] = turnRight(chain[i])
    # 반시계 방향
    elif d == -1:
        chain[i] = turnLeft(chain[i])

for _ in range(k):
    idx, direction = map(int, input().split())
    idx -= 1
    check = [0]*4
    check[idx] = direction
    # 왼쪽 톱니바퀴 확인
    # for i in range(1, 4):
    for i in range(idx, 0, -1):
        if chain[i][6] != chain[i-1][2]:
            check[i-1] = (-1)*check[i]
    # 오른쪽 톱니바퀴 확인
    for i in range(idx, 3):
        if chain[i][2] != chain[i+1][6]:
            check[i + 1] = (-1)*check[i]
    for i in range(4):
        move(i, check[i])

res = 0
for i in range(4):
    if chain[i][0] == '1':
        res += 2**i
print(res)

연쇄적으로 작용하는 방식을 구현하기 위해 check 배열을 사용하였다.

이때 중요한 것은 왼쪽, 오른쪽 톱니바퀴를 검사할 때 범위를 잘 확인하는 것이다.

예를 들어, 1번째(idx=0) 톱니바퀴는 왼쪽 톱니바퀴가 존재하지 않으므로 왼쪽 톱니바퀴 검사시 제외해주어야 한다.

마찬가지로 4번째(idx=3) 톱니바퀴 또한 오른쪽 톱니바퀴가 없기에 오른쪽 톱니바퀴 검사시 열외한다.

입력값으로 들어온 direction으로부터 한칸씩 왼쪽으로 한칸씩 오른쪽으로 검사해주어야 하기 때문에

왼쪽 톱니바퀴 검사시 for문을

for i in range(idx, 4):

와 같이 구현하면 문제가 발생한다. 한칸씩 왼쪽으로 이동하며 검사해주어야 하기 때문에 기준 idx로부터 idx = 1까지 검사하도록

 for i in range(idx, 0, -1):

와 같이 구현해주어야 정상 동작한다. 

 

[코드 개선]

만약 처음 톱니바퀴를 chain이라는 배열에 넣을 때 문자열이 아닌 리스트 형식으로 입력값을 받는다면

turnLeft, turnRight 함수에서 pop(), insert() 함수를 사용할 수 있다. 메모리는 비슷하나 시간이 10ms 정도 단축된 것을 확인해볼 수 있었다. 

# 문자열이 아닌 리스트로 입력 받음 
# [['1', '0', '1', '0'], .., ['1', 1', '0', '0']]
chain = [list(input()) for _ in range(4)]
k = int(input())
# 왼쪽으로 회전
def turnLeft(s):
    data = s.pop(0)
    s.append(data)
    return s
# 오른쪽을 회전
def turnRight(s):
    data = s.pop()
    s.insert(0, data)
    return s
def move(i, d):
    # 시계 방향
    if d == 1:
        chain[i] = turnRight(chain[i])
    # 반시계 방향
    elif d == -1:
        chain[i] = turnLeft(chain[i])

for _ in range(k):
    idx, direction = map(int, input().split())
    idx -= 1
    check = [0]*4
    check[idx] = direction
    # 왼쪽 톱니바퀴 확인
    for i in range(idx, 0, -1):
        if chain[i][6] != chain[i-1][2]:
            check[i-1] = (-1)*check[i]
    # 오른쪽 톱니바퀴 확인
    for i in range(idx, 3):
        if chain[i][2] != chain[i+1][6]:
            check[i + 1] = (-1)*check[i]
    for i in range(4):
        move(i, check[i])

res = 0
for i in range(4):
    if chain[i][0] == '1':
        res += 2**i
print(res)

 

2. 틀린 풀이 

아래와 같이 일반적인 구조는 완성하였으나 연쇄적으로 동작하는 방법이 떠오르지 않아서 아이디어를 참고하였다.

check라는 배열로 각 톱니바퀴 별 회전 여부를 검사하고 싶었는데 이 부분을 구현하지 못했다. 

chain = [input() for _ in range(4)]
k = int(input())

def turnLeft(s):
    data = s[1:] + s[0]
    return data

def turnRight(s):
    data = s[-1] + s[:-1]
    return data

def move(i, d):
    # 시계 방향
    if d == 1:
        chain[i] = turnRight(chain[i])
    # 반시계 방향
    elif d == -1:
        chain[i] = turnLeft(chain[i])
 
for _ in range(k):
    idx, direction = map(int, input().split())
    idx -= 1
    # 옆으로 퍼지게 하는 것은 어떻게 구현하지? 연쇄작용
    check = [False]*4
    if idx == 0:
        move(idx, direction)
        # 옆동네 방문
        if not check[idx + 1] and chain[idx][2] != chain[idx+1][6]:
            move(idx+1, -1*direction)
    if idx == 3:
        move(idx, direction)
        # 옆동네 방문 
        if not check[idx - 1] and chain[idx][6] != chain[idx - 1][2]:
            move(idx-1, -1 * direction)
    if idx == 2 or idx == 1:
        # 시계 방향
        move(idx, direction)
        # 옆동네 방문
        if not check[idx - 1] and chain[idx][6] != chain[idx - 1][2]:
            move(idx-1, -1*direction)
        # 옆동네 방문
        if not check[idx + 1] and chain[idx][2] != chain[idx + 1][6]:
            move(idx + 1, -1*direction)