도와주세요

[파이썬] 소용돌이(?) 코딩이 어렵네요 ㅠㅠ

이니스프리2020.02.14 22:06조회 수 101댓글 6

  • 1
    • 글자 크기



코딩 문제 중에서 소용돌이(?)라는게 있던데요.


위 그림처럼 n*n 사이즈의 2차원 리스트에 시계방향으로 1부터 n^2까지 자연수를 순서대로 배열하는 문제입니다.


며칠동안 고민을 했는데 잘 해결되지 않아서 COS 시험을 앞두고 질문 드립니다 ㅠㅠ


구글링해보면 이 문제 때문에 다들 고생했다는 내용이 있네요 ㅜㅜ



우선 COS Pro 홈페이지의 모범답안의 풀이입니다.


정수 n을 받아서 n*n 사이즈의 소용돌이를 반환하는 함수입니다.


def in_range(i, j, n):
    return 0 <= i and i < n and 0 <= j and j < n

def 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]을 출력하네요.


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 False

def 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 씩 이동하는 패턴을 활용하는 방법은 없을까요??


ཇོ་མོ་གླང་མ

  • 1
    • 글자 크기
  • 2020.2.14 23:48

    파이썬의 앝은 복사로 인해 생기는 버그라고 생각하시면 됩니다.


    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])



    그래서 해당 부분만 수정해주면 정상적으로 돌아갑니다.


    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 False
     
    def sol(n):
        s=[[0]*n for _ in range(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



  • @humit
    이니스프리글쓴이
    2020.2.15 00:03

    ㅎㄷㄷ 얕은 복사와 관련해서 이런 문제가 있었군요!

    며칠동안 이 문제를 비롯하여 유사한 문제들이 안 풀려서 고민했는데 알려주셔서 감사합니다!!

    그냥 리스트의 곱셈을 하는 것과 for문으로 돌리는게 다르다는 것을 humit 님 덕분에 처음으로 알았네요 ^^

     

    구체적인 원리까지는 제가 아직 이해하지 못했지만

    구글링해보니 대략 "2차원 이상 리스트부터는 내부는 깊은 복사가 안되고 얕은 복사만 된다"는 취지로 써있던데

    그렇다면 1차원 리스트는 곱셈으로 해결해도 되고, 그 이상은 for문을 사용해야 된다고 일단 시험을 앞두고 이해하면 될까요?? ㅠㅠ

     

    그럼 즐거운 주말 되시고, 일욜부터 추워진다는데 감기 조심하세요!! ^^

  • @이니스프리
    2020.2.15 00:09

    네 그런식으로 이해하시면 되겠습니다.

  • @humit
    이니스프리글쓴이
    2020.2.15 00:14

    옙 감사합니다!

    덕분에 시험 잘 준비할게요~

    샘플 문제를 보니 COS Pro 1급은 저같은 아마추어가 도전할 시험은 아닌 것 같더군요 ㄷㄷ

    그럼 굿밤 되세요! ^-^

  • 2020.2.15 00:17

    이니스프리님이 원하시는 방법과는 약간의 차이가 있긴 하지만 다음과 같이 한방향으로 연속적으로 할당하는 방법이 있습니다.



    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
    이니스프리글쓴이
    2020.2.15 00:22

    앗 이렇게 양파껍질 벗기듯이 순서대로 한 바퀴씩 처리하는 방법이 이동할 때 체크할 요소가 적어서 더욱 간단명료하네요! ^^

    바쁘신데 정말 감사합니다!!

    유사한 문제에서 이런 풀이방법을 적용해봐야겠네요~

    그럼 안녕히 주무세요~ ^-^

댓글 달기

번호 제목 글쓴이 날짜 조회 수
공지 [중요] sfuh.tk 기본 제공 도메인 사용하는 분들 확인해주시기 바랍니다.8 마스터 2019.12.29 676
공지 회원 전용 페이지가 생겼습니다.17 마스터 2018.03.20 12163
공지 [필독] 질문하는 방법17 마스터 2018.02.23 1848
713 히어로 무비 추천 부탁드립니다!30 이니스프리 2019.10.29 193
712 흠.. 여기가 빠른 답변이 가능할까요?3 워시퍼 2019.02.26 103
711 후이즈 도메인 3년 연장 하자마자 이상한일이...3 참비 2018.10.21 107
710 회원가입 이 외안되는거애요?5 핫슈 2016.10.14 168
709 홈서버용 CPU 좀 봐주시면 감사하겠습니다~ ㅠㅠ7 이니스프리 2020.02.24 64
708 홈... 이런게 가능할까요?21 모니터 2017.10.10 280
707 혹시..3 막시모 2018.02.27 137
706 혹시 호스트 차원에서 IP차단도 지원이 되나요?2 Nodeulnaru 2017.02.27 217
705 혹시 크롬 '개발자 도구' 잘 사용하시는 분이 있을까요? 질문이 있어서요.16 JAVA 2017.11.10 454
704 혹시 지금 호스팅 신청이 안되는건가요?2 Doge아시다시피 2017.07.23 165
703 혹시 이거 툴 프로그램 뭔지 아시는분 계신가요?6 JAVA 2017.11.13 255
702 혹시 워드프레스 메인페이지 위젯 출력 어캐하나요?4 title: 크롬핫슈 2017.09.05 236
701 혹시 반디캠으로 찍은 영상 도 올릴수잇습니까?3 title: 크롬핫슈 2018.04.09 170
700 혹시 XE 쓰시는분들중에 앱 만들어서 쓰시는 분 계신가요!?2 준그루 2017.10.01 202
699 혹시 frame 태그로 php 삽입 가능한가요?9 Seia 2017.11.06 251
698 혹시 ajax chat 사용해보신분?1 막시모 2016.11.17 226
697 호스팅패널에서 서브도메인 사용하시는 분 계신가요?2 joyfuI 2019.08.28 127
696 호스팅중에4 BJ엠지 2017.08.24 181
695 호스팅을할떄에5 Sein&Music 2016.10.27 267
694 호스팅을 신청할려고 하는대 어느걸써야 이득이죠?4 AA 2017.07.29 209
이전 1 2 3 4 5 6 7 8 9 10... 36다음
첨부 (1)
1581684920342.jpg
24.1KB / Download 2
서버에 요청 중입니다. 잠시만 기다려 주십시오...