도와주세요

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

이니스프리2020.02.14 22:06조회 수 98댓글 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
    • 글자 크기
다른 기기에서의 사이트 접속 불가 (by 논문쓰는중3) XE 상단바 내려가게 만들기 (by 논문쓰는중3)
  • 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 기본 제공 도메인 사용하는 분들 확인해주시기 바랍니다.6 마스터 2019.12.29 632
공지 회원 전용 페이지가 생겼습니다.17 마스터 2018.03.20 12157
공지 [필독] 질문하는 방법17 마스터 2018.02.23 1830
689 클라우드 플레어를 특정 PHP 파일에 연계되도록 설정할 수도 있는가요?? 이니스프리 2020.02.21 45
688 에러 523 해결법4 논문쓰는중3 2020.02.21 123
687 사이트 접속 불가5 논문쓰는중3 2020.02.21 62
686 고정된 요일에 카운트다운되는 소스가있나요?4 슬기 2020.02.20 48
685 그누보드에서 과도한 POST 요청을 보내는 매크로를 이용한 DDoS에 대해 질문 드립니다.6 이니스프리 2020.02.20 89
684 윈도우 서버를 VPS에 구축하는 것에 대해 질문 드립니다.23 이니스프리 2020.02.17 204
683 다른 기기에서의 사이트 접속 불가4 논문쓰는중3 2020.02.17 65
[파이썬] 소용돌이(?) 코딩이 어렵네요 ㅠㅠ6 이니스프리 2020.02.14 98
681 XE 상단바 내려가게 만들기2 논문쓰는중3 2020.02.14 66
680 스터디포어스에서 VisualEditor 사용이 가능하나요?2 논문쓰는중3 2020.02.12 68
679 컴퓨터 전문가님들 봐주세요~~원격프로그램에 대해서입니다9 매매의신 2020.02.12 114
678 인스타 프로필 사진 퍼오는거?3 슬기 2020.02.11 56
677 VPS에서 LEMP 스택을 제공하면 이걸 그대로 사용해도 괜찮을까요??4 이니스프리 2020.02.07 76
676 이 파이썬 강좌를 수강하는 것은 어떨지 여쭤봅니다 ^^6 이니스프리 2020.01.31 76
675 제대로 작동하는 GIF 무료 이미지 호스팅 사이트 추천 부탁드려요! 이니스프리 2020.01.31 35
674 리눅스 오프라인 강좌의 수업 내용과 관련하여 질문 드립니다.10 이니스프리 2020.01.30 85
673 가개통을 구매하는데에 특별한 문제가 있나요?3 Seia 2020.01.26 73
672 ReactJS 도와주세요!2 title: 투명 아이콘Hanam09 2020.01.25 69
671 선택약정 안 되는 중고폰의 경우에는 어떤 단점이 있는 것인가요??6 이니스프리 2020.01.21 371
670 맥북 프로 구매와 관련하여 여쭤봅니다4 이니스프리 2020.01.20 78
이전 1 2 3 4 5 6 7 8 9 10... 36다음
첨부 (1)
1581684920342.jpg
24.1KB / Download 2
서버에 요청 중입니다. 잠시만 기다려 주십시오...