먹고 기도하고 코딩하라

[백준] 17406 : 배열 돌리기 4 (Python3) 본문

자료구조&알고리즘/BOJ

[백준] 17406 : 배열 돌리기 4 (Python3)

2G Dev 2022. 2. 15. 09:24
728x90
728x90

 

 

17406번: 배열 돌리기 4

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의

www.acmicpc.net

 

보고.. 헐.. 제가 이 문제를 풀 수 있을까요? 했는데 50분만에 풀었다. 늘고 있다는 증거 같아서 흐뭇.. 또 다행..

이 문제는 예전에 푼 "미세먼지 안녕!" 문제와 비슷하게, 배열을 사각형으로 돌리는 문제이다. 차이가 있다면 미세먼지 문제는 청정기가 있는 가로줄부터 맨위 혹은 맨아랫줄까지 테두리만 이동한다면 이 문제는 그 테두리 안의 사각형까지 또 돌려줘야 한다는 점이다. 그래도 이런 문제도 자주 풀다보니 어떻게 푸는지 좀 알겠고 반갑달까..

 

자 일단, 구해야 하는 것은 배열의 값이다. 배열의 값이란, 각 가로줄(행! 맨날 헷갈린다)의 합 중 가장 작은 값을 말한다. 즉, sum(row) 해서 min 값을 구해주면 된다는 의미이다.

입력으로는 배열 다음 K개만큼의 회전 연산이 들어오는데, 회전 연산은 r, c, s 순서로 들어오게 된다. 회전하게 되는 정사각형 범위를 구하는 방법은, 맨 왼쪽 상단 꼭지점을 [r-s, c-s], 맨 오른쪽 하단 꼭지점을 [r+s, c+s]로 풀면 된다.  

만약 회전 연산이 [3, 4, 2]라면 회전하게 될 정사각형 범위는 [3-2, 4-2]부터 [3+2, 4+2], 즉 [1, 2]부터 [5, 6] 안쪽 모든 좌표이다. 이건 예시가 더 이해하기 쉬우므로 예시 사진을 첨부한다.

아랫줄, 회전 연산이 2개 이상이라면 연산을 수행한 순서에 따라 최종 배열이 다르다고 했다.

이건 무슨 뜻인가? 모든 순열을 다 시험해보라는 것이다. 즉... 완전탐색 문제다.

자 이제 코드로 넘어가보겠다. 알고리즘 스터디 때 하는 것처럼 코드를 조각내서 설명하겠다. (스터디가 없을 때는 친구가 선물해진 춘식이 인형이 내 러버덕이다)

먼저, 입력을 받아야 한다. 그리고 배열을 회전해야 하기 때문에 시계 방향의 방향 벡터가 있으면 좋을 것이다. 답이 될 변수는 최대값으로 선언해준다.

from itertools import permutations
from copy import deepcopy

N, M, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
RCS = [list(map(int, input().split())) for _ in range(K)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
res = 1e9

permutations를 import한 이유는 회전 연산이 2개 이상일 때는 모든 순열을 다 시험해 봐야 하기 때문이다. 파이썬에는 permutations라는 사기급 내장 메소드가 있으므로 이것을 사용한다. 만약 [3, 4, 2], [4, 2, 1]이 들어와서 permutations를 하면 기특하게도 [3, 4, 2], [4, 2, 1]과 [4, 2, 1], [3, 4, 2] 모두 테스트할 수 있다.

deepcopy를 import한 이유는, 순열마다 배열의 최종 생김새가 다른데 이것을 그대로 사용하면 안 되고 원본 배열을 사용해야 하기 때문이다. 나는 그때그때 순열의 시작에서 temp로 A를 deepcopy해줘서 A를 원본 그대로 보존한 채로 사용했다.

 

다음으로 넘어가자.

for perm in permutations(RCS,K):
  temp = deepcopy(A)
  for r, c, s in perm:
    for i in range(0, s):
      top = [r-s+i-1, c-s+i-1]
      bottom = [r+s-i-1, c+s-i-1]
      nx, ny = top
      tmp = temp[nx][ny]

앞서 말했던 것처럼 순열 조합을 테스트해봐야 한다. perm은 [[[3, 4, 2], [4, 2, 1]], [[4, 2, 1], [3, 4, 2]]]가 되고 r, c, s는 3, 4, 2와 4, 2, 1이 된다. 바깥 for문은 한 순열의 순서이고 안쪽 for문은 그 순열 내에서 회전 연산 1개를 뜻한다.

원본 배열을 보존해야 하기 때문에 temp로 A를 복사한다.

그 다음, 회전 연산에서 변수가 되는 s로 for 루프를 돌려준다. 이건 왜 그렇냐면, 예제를 잘 관찰해보면 s번만큼 테두리 회전 연산을 하게 되기 때문이다.

이 경우는 (3, 4, 2)이기 때문에 사각형 2개의 회전이 있다. (4, 2, 1)은 같은 논리로 정사각형 1개 테두리만큼 회전하게 된다.

근데 불행히도 [1, 2], [5, 6]이기 때문에... 이렇게 하면 리스트를 벗어난다. 방법은 2가지다. 더미 0을 붙여서 크기를 맞춰주거나 아니면 1을 빼거나. 1차원일 때는 0을 붙여도 괜찮지만 나는 2차원일 때는 웬만하면 그냥 1 빼서 숫자를 맞추는 편이다. 

top은 최상단의 맨 왼쪽 꼭지점 좌표, bottom은 최하단의 맨 오른쪽 꼭지점 좌표가 된다. 이건 for 루프를 돌면서 줄어들게 되어 있으니 크게 신경쓰지 않아도 된다. 말했던 것처럼, top에는 s를 더하고 bottom에는 s를 빼야 정사각형이 줄어든다. 1은 list index error를 방지하기 위해 기본으로 빼준다. 맨 왼쪽부터 시작하기 위해 nx, ny를 할당하고, 이 값도 미리 tmp로 들고 있는다.

 

      for i in range(4):
        while True:
          nx = nx + dx[i]
          ny = ny + dy[i]
          if not (nx >= top[0] and nx <= bottom[0] and ny >= top[1] and ny <= bottom[1]):
            nx = nx - dx[i]
            ny = ny - dy[i]
            break
          tmp, temp[nx][ny] = temp[nx][ny], tmp

 여기서 한 스콥 더 들어가서 for문을 돈다. 이 for문은 방향 벡터를 따라 시계 방향으로 회전하며 값을 바꾸는 for문이다. while True를 한 이유는 회전 연산에서 제시하는 맨 끝점까지 일자로 따라가면서 값을 계속 바꿔야 하기 때문이다. 보통은 0, N-1 이런 식으로 범위 계산을 하는데 여기서는 top, bottom의 좌표 안쪽으로만 이동해야 하기 때문에 if문 안쪽 조건이 조금 다르다는 것만 유의하면 될 것 같다.

tmp, temp[nx][ny] = temp[nx][ny], tmp 하게 되면 변수를 하나 더 쓰지 않고도 값을 서로 바꿔서 홀드할 수 있기 때문에 좋다.

이렇게 짜면 무한 루프가 걸리는 거 아닐까 할 수도 있는데 애초에 i의 range가 0~3이기 때문에 while문에서 4번 탈출하고 나면 동남서북 모든 방향을 다 돌고 난 이후라 상관없다.

 

  for row in temp:
    res = min(res, sum(row))
print(res)

어쨌든 이대로 내버려두면 한 순열의 모든 회전 연산을 저절로 마치게 된다. 한 순열을 전부 테스트해봤다면 그 순열이 있은 다음의 최소값을 계산해야 하기 때문에 한 줄씩 sum을 계산해서 res와 비교해, sum이 작다면 res를 더 작은 값인 sum으로 업데이트한다.

그리고 마지막에 res를 출력하고 끝낸다.

 

다음은 전체 코드이다.

from itertools import permutations
from copy import deepcopy

N, M, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
RCS = [list(map(int, input().split())) for _ in range(K)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
res = 1e9

for perm in permutations(RCS,K):
  temp = deepcopy(A)
  for r, c, s in perm:
    for i in range(0, s):
      top = [r-s+i-1, c-s+i-1]
      bottom = [r+s-i-1, c+s-i-1]
      nx, ny = top
      tmp = temp[nx][ny]

      for i in range(4):
        while True:
          nx = nx + dx[i]
          ny = ny + dy[i]
          if not (nx >= top[0] and nx <= bottom[0] and ny >= top[1] and ny <= bottom[1]):
            nx = nx - dx[i]
            ny = ny - dy[i]
            break
          tmp, temp[nx][ny] = temp[nx][ny], tmp

  for row in temp:
    res = min(res, sum(row))
print(res)

 

 

얼마 전에 이종립 개발자님이 코딩테스트를 어떻게 푸셨는지를 보게 됐는데 왜 이렇게 풀었는지 주석을 꼼꼼히 적으신다는 말을 듣고 나도 실천해봐야지 했다. 그런데 막상 문제를 접하니 단편적인 정보만 잡아서 코드를 짜고 다시 문제로 돌아오고 하는 일이 많아지더라. 어려운 문제를 풀 때는 가끔 종이에 메모를 하면서 풀곤 하는데 코드 에디터에서도 그렇게 주석을 작성하면서 풀 수 있도록 내일부터 노력해야겠다. 먼 길일수록 돌아가자.. 

 

 

728x90
반응형
0 Comments
댓글쓰기 폼