[BOJ] 17406 - 배열 돌리기 4

사용 언어: Python3

문제

백준 17406

내 풀이

첫 번째

N, M, K = map(int, input().split())
lst = [list(input().split()) for _ in range(N)]

# 배열은 1행 1열부터 시작!
def rotate(lst, r, c, s, N, M):
  for i in range(r-s-1, r+s):
    for j in range(c-s-1, c+s):
      # 시계 방향으로 한 칸 회전을 어떻게 하지..
      lst[][] = lst[i][j]
      # lst[j][(r+s-1)-i] = lst[i][j]
      
def findMin(lst, N, M):
  # 각 행 합의 최소
  num = [[int(lst[i][j]) for j in range(M)] for i in range(N)]
  return min([sum(row) for row in num])

for _ in range(K):
  r, c, s = map(int, input().split())
  rotate(lst, r, c, s, N, M)
print(findMin(lst, N, M))

두 번째 - 0407 추가

from copy import deepcopy

N, M, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
Q = [tuple(map(int, input().split())) for _ in range(K)]

def findMin(mp):
  return min([sum(row) for row in mp])

# 남 서 북 동 (시계)
dx, dy = [1,0,-1,0], [0,-1,0,1]
def rotate(qry, mp):
  (r, c, s) = qry
  r, c = r-1, c-1 # r,c는 회전의 중심
  copyMp = deepcopy(mp)

  for i in range(1,s+1):
    rr, cc = r-i, c+i # rr,cc는 새로운 출발점
    for w in range(4):
      for j in range(i*2):
        rrr,ccc = rr+dx[w], cc+dy[w] # 각 방향으로 이동
        copyMp[rrr][ccc] = mp[rr][cc]
        rr, cc = rrr, ccc # 다음으로 업데이트
  return copyMp
    
def dfs(mp, qry_check):
  global ans
  if sum(qry_check) == K:
    ans = min(ans, findMin(mp))
    return
  for i in range(K):
    if qry_check[i] == 1:
      continue
    new_mp = rotate(Q[i], mp)
    qry_check[i] = 1
    dfs(new_mp, qry_check)
    qry_check[i] = 0 # 백트래킹

ans = 10000
ckQry = [0 for _ in range(K)] # 각각의 쿼리를 수행했는지 체크
dfs(A, ckQry)
print(ans)

다른 사람 풀이

리스트 이용

from copy import deepcopy

N, M, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
Q = [tuple(map(int, input().split())) for _ in range(K)] # (r, c, s) 튜플 형태로 Query 받음

ans = 10000

def findMin(lst):
  return min([sum(row) for row in lst])

# 회전 방향: 남 -> 서 -> 북 -> 동
dx, dy = [1,0,-1,0], [0,-1,0,1]
def rotate(lst, qry):
  (r, c, s) = qry # r,c는 회전의 중심점
  r, c = r-1, c-1 # 문제에는 1행1열부터로 정의했기 때문
  copy_lst = deepcopy(lst)
  for i in range(1, s+1): # 중심점은 변환 안되기 때문에 1부터 시작
    rr, cc = r-i, c+i # 출발 지점 (중심점에서 오른쪽 대각선 방향으로 한 칸씩 이동)
    for w in range(4): # 방향마다
      for d in range(i*2): # 한 변의 길이는 중심에서의 거리 * 2
        rrr, ccc = rr+dx[w], cc+dy[w]
        copy_lst[rrr][ccc] = lst[rr][cc]
        rr, cc = rrr, ccc
  return copy_lst
  
def dfs(lst, qry):
  global ans
  if sum(qry) == K: # 쿼리를 다 처리한 경우 (쿼리는 1로 체크하기 때문에 sum 이용)
    ans = min(ans, findMin(lst))
    return
  for i in range(K):
    if qry[i]: # 쿼리가 체크되어 있다면 넘어가기
      continue
    new_lst = rotate(lst, Q[i]) # 쿼리[i]를 사용해 lst를 회전
    qry[i] = 1 # 쿼리 처리 완료
    dfs(new_lst, qry)
    qry[i] = 0 # 백트래킹
    

dfs(A, [0 for i in range(K)]) # K는 쿼리 개수

print(ans)

비트마스크(bitmask) 이용

from copy import deepcopy

N, M, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
Q = [tuple(map(int, input().split())) for _ in range(K)] # (r, c, s) 튜플 형태로 Query 받음

def findMin(lst):
  return min([sum(row) for row in lst])

# 회전 방향: 남 -> 서 -> 북 -> 동
dx, dy = [1,0,-1,0], [0,-1,0,1]
def rotate(lst, qry):
  (r, c, s) = qry # r,c는 회전의 중심점
  r, c = r-1, c-1 # 문제에는 1행1열부터로 정의했기 때문
  copy_lst = deepcopy(lst)
  for i in range(1, s+1): # 중심점은 변환 안되기 때문에 1부터 시작
    rr, cc = r-i, c+i # 출발 지점 (중심점에서 오른쪽 대각선 방향으로 한 칸씩 이동)
    for w in range(4): # 방향마다
      for d in range(i*2): # 한 변의 길이는 중심에서의 거리 * 2
        rrr, ccc = rr+dx[w], cc+dy[w]
        copy_lst[rrr][ccc] = lst[rr][cc]
        rr, cc = rrr, ccc
  return copy_lst
  
def dfs(lst, qry, st):
  # 만약 쿼리가 6개이고 다 처리했다면
  # 111111
  # 이것은 이진수 표기로 (1000000 - 1)와 같음
  if st == (1 << K) - 1: # 쿼리를 다 처리한 경우
    return findMin(lst)
  ans = 10000
  for i in range(K):
    if st & 1 << i == 0:
      ans = min(ans, dfs(rotate(lst, Q[i]), qry, st | 1 << i))
  return ans    

print(dfs(A, Q, 0))

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기