- 6
- 이니스프리
- 조회 수 2809
코딩 문제 중에서 소용돌이(?)라는게 있던데요.
위 그림처럼 n*n 사이즈의 2차원 리스트에 시계방향으로 1부터 n^2까지 자연수를 순서대로 배열하는 문제입니다.
며칠동안 고민을 했는데 잘 해결되지 않아서 COS 시험을 앞두고 질문 드립니다 ㅠㅠ
구글링해보면 이 문제 때문에 다들 고생했다는 내용이 있네요 ㅜㅜ
우선 COS Pro 홈페이지의 모범답안의 풀이입니다.
정수 n을 받아서 n*n 사이즈의 소용돌이를 반환하는 함수입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | def in_range(i, j, n): return 0 <= i and i < n and 0 <= j and j < ndef solution(n): pane = [[0 for j in range(n)] for i in range(n)] dy = [0, 1, 0, -1] dx = [1, 0, -1, 0] ci, cj = 0, 0 num = 1 while in_range(ci, cj, n) and pane[ci][cj] == 0: for k in range(4): if not in_range(ci, cj, n) or pane[ci][cj] != 0: break while True: pane[ci][cj] = num num += 1 ni = ci + dy[k] nj = cj + dx[k] if not in_range(ni, nj, n) or pane[ni][nj] != 0: ci += dy[(k + 1) % 4] cj += dx[(k + 1) % 4] break ci = ni cj = nj return pane |
위 코드와 비슷한 방식으로 제가 작성하려고 했던 코드인데 제대로 작동하지 않네요.
예컨대 3을 넣으면
[1,9,8]
[1,9,8]
[1,9,8]을 출력하네요.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | def check(a, b, s, n): # 0 <= a, b < n이고, 이미 지나간 경로가 아님을 확인합니다. if 0<=a<n and 0<=b<n and s[a][b] == 0: return True else: return Falsedef sol(n): s=[[0]*n]*n da=[0, 1, 0, -1] # a는 y축입니다. db=[1, 0, -1, 0] # b는 x축입니다. a=b=0 # 현재 좌표를 의미합니다. cnt=1 # 1부터 n^2까지 카운트합니다. d=0 # da, db의 인덱스를 가리키는 변수입니다. while cnt<=n**2: s[a][b]=cnt # 현재 카운트를 s에 대입합니다. ta=a+da[d] tb=b+db[d] if check(ta, tb, s, n): # 움직이는 방향이 문제없는지 체크합니다. a=ta b=tb else: # 문제가 있으면 방향을 변경합니다. d=(d+1)%4 a+=da[d] b+=db[d] cnt+=1 return s |
(a, b) 좌표를 찍어보면 틀리긴 하던데 제가 어디에서 잘못했는지 잘 모르겠네요 ㅠㅠ
어떻게 풀어야 간명하게 해결되는지 여쭤봅니다.
스포어 회원분들께 항상 감사드립니다! ^-^
+) 한 방향으로 4 -> 3 -> 3 -> 2 -> 2 -> 1 -> 1 씩 이동하는 패턴을 활용하는 방법은 없을까요??
작성자
댓글 6
humit 
신고
"humit님의 댓글"
이 댓글을 신고 하시겠습니까?
ㅎㄷㄷ 얕은 복사와 관련해서 이런 문제가 있었군요!
며칠동안 이 문제를 비롯하여 유사한 문제들이 안 풀려서 고민했는데 알려주셔서 감사합니다!!
그냥 리스트의 곱셈을 하는 것과 for문으로 돌리는게 다르다는 것을 humit 님 덕분에 처음으로 알았네요 ^^
구체적인 원리까지는 제가 아직 이해하지 못했지만
구글링해보니 대략 "2차원 이상 리스트부터는 내부는 깊은 복사가 안되고 얕은 복사만 된다"는 취지로 써있던데
그렇다면 1차원 리스트는 곱셈으로 해결해도 되고, 그 이상은 for문을 사용해야 된다고 일단 시험을 앞두고 이해하면 될까요?? ㅠㅠ
그럼 즐거운 주말 되시고, 일욜부터 추워진다는데 감기 조심하세요!! ^^
신고
"이니스프리님의 댓글"
이 댓글을 신고 하시겠습니까?
humit
→ 이니스프리
네 그런식으로 이해하시면 되겠습니다.
신고
"humit님의 댓글"
이 댓글을 신고 하시겠습니까?
옙 감사합니다!
덕분에 시험 잘 준비할게요~
샘플 문제를 보니 COS Pro 1급은 저같은 아마추어가 도전할 시험은 아닌 것 같더군요 ㄷㄷ
그럼 굿밤 되세요! ^-^
신고
"이니스프리님의 댓글"
이 댓글을 신고 하시겠습니까?
humit 이니스프리님이 원하시는 방법과는 약간의 차이가 있긴 하지만 다음과 같이 한방향으로 연속적으로 할당하는 방법이 있습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | def sol(n): arr = [[None] * n for _ in range(n)] dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] x, y = 0, 0 idx = 1 side = n - 1 while side > 0: for direction in range(4): for _ in range(side): arr[y][x] = idx x += dx[direction] y += dy[direction] idx += 1 # 위의 for문을 시작한 위치 그대로 돌아오므로 # x와 y 값을 1씩 증가시키면 다음 위치가 됩니다. x += 1 y += 1 side -= 2 # 1칸만 남은 경우(변의 길이가 홀수인 경우) 바로 채워줍니다 if side == 0: arr[y][x] = idx return arr |
while문을 한 번 돌 때마다 바깥쪽에 있는 사각형에 숫자가 채워지는 방식으로 동작합니다. 그래서 side 값이 2씩 감소를 하는 것이고요.
뭔가 양파껍질을 벗겨 나가는 것과 유사한 방식으로 동작한다고 생각하시면 됩니다.
신고
"humit님의 댓글"
이 댓글을 신고 하시겠습니까?
앗 이렇게 양파껍질 벗기듯이 순서대로 한 바퀴씩 처리하는 방법이 이동할 때 체크할 요소가 적어서 더욱 간단명료하네요! ^^
바쁘신데 정말 감사합니다!!
유사한 문제에서 이런 풀이방법을 적용해봐야겠네요~
그럼 안녕히 주무세요~ ^-^
신고
"이니스프리님의 댓글"
이 댓글을 신고 하시겠습니까?
슬기
파이썬의 앝은 복사로 인해 생기는 버그라고 생각하시면 됩니다.
a=[[0]]*5# 생각과 다르게 해당 부분은 True를 반환합니다.# 즉 a[0]와 a[2]는 서로 같은 곳을 가리킨다고 생각하시면 됩니다.print(id(a[0])==id(a[2]))a[0][0]=2# 그래서 a[0][0]를 바꾸었지만 a[2][0]가 동시에 바뀌게 됩니다.# 나머지 원소들도 동일하게 2로 바뀝니다.print(a[2][0])그래서 해당 부분만 수정해주면 정상적으로 돌아갑니다.
defcheck(a, b, s, n):# 0 <= a, b < n이고, 이미 지나간 경로가 아님을 확인합니다.if0<=a<nand0<=b<nands[a][b]==0:returnTrueelse:returnFalsedefsol(n):s=[[0]*nfor_inrange(n)]da=[0,1,0,-1]# a는 y축입니다.db=[1,0,-1,0]# b는 x축입니다.a=b=0# 현재 좌표를 의미합니다.cnt=1# 1부터 n^2까지 카운트합니다.d=0# da, db의 인덱스를 가리키는 변수입니다.whilecnt<=n**2:s[a][b]=cnt# 현재 카운트를 s에 대입합니다.ta=a+da[d]tb=b+db[d]ifcheck(ta, tb, s, n):# 움직이는 방향이 문제없는지 체크합니다.a=tab=tbelse:# 문제가 있으면 방향을 변경합니다.d=(d+1)%4a+=da[d]b+=db[d]cnt+=1returns