inflearn logo
강의

Khóa học

Chia sẻ kiến thức

Giới thiệu về giải bài toán bằng thuật toán Python (chuẩn bị cho bài kiểm tra viết mã)

10. Điều hướng mê cung (DFS)

깊은 복사 얕은 복사?

Đã giải quyết

303

rlarhkd9900617

3 câu hỏi đã được viết

0

안녕하세요 태원님!  강의 잘 보고있습니다. 미로 탐색을 강의 보기전에 다음과 같이 풀었었는데  자꾸             if not (ncol, nrow) in path:  부분이 참이 되면서 방문했던 곳을 다시 방문하더군요.. 아무래도 깊은복사와 얕은 복사에 관련이 있는것 같아서 아래부분으로 수정하니까 정상적으로 실행이 되었습니다만 저 과정에서 문제가 어떤 것인지 명확하게 이해가 되지 않습니다. DFS의 인자로 바로 path+[(nrow,ncol)]를 주면  안되는 이유가 뭘까요? 머리아프네요 ㅠㅠ

# 벽을 만들었다가 없애는 아이디어는 정말 대단하네요.. ㅠㅠ 많은 문제를 풀어봐야겠다는 생각이듭니다.

from copy import deepcopy
N = 7
Map = []
for i in range(N):
    Map.append(list(map(int, input().split())))

def DFS(path):
    global cnt
    x, y= path[-1]
    if (x, y) == (N-1, N-1):
        cnt += 1
        return
    
    for i, j in [(1,0), (0,1), (-1,0), (0,-1)]:
        if (x+i, y+j) != (0,0) and 0<=x+i<N and 0<=y+j<N and Map[x+i][y+j] == 0:
            if not (x+i, y+j) in path: ### 여기가 문제!
                print((x+i, y+j) not in path)
                DFS(path+[(x+i,y+j)]) 

            #위 부분에서 not (x+i, x+j) in path가 자꾸 참이 됨
            #위 if 단락을 아래와 같이 바꾸면 답이 나옴
            #if (x+i, y+j) not in path :
            #    npath = deepcopy(path)
            #    npath.append((x+i,y+j))
            #    DFS(npath)
 
cnt = 0          
DFS([(0,0)])
print(cnt)

python 코테 준비 같이 해요!

Câu trả lời 2

1

codingcamp

  "if not (ncol, nrow) in path:  부분이 참이 되면서 방문했던 곳을 다시 방문하더군요.. 아무래도 깊은복사와 얕은 복사에 관련이 있는것 같아서 아래부분으로 수정하니까 정상적으로 실행이 되었습니다만 저 과정에서 문제가 어떤 것인지 명확하게 이해가 되지 않습니다. DFS의 인자로 바로 path+[(nrow,ncol)]를 주면  안되는 이유가 뭘까요?" 

질문에서 DFS 인자로 path+[(nrow, ncol)] 로 넘기는 데  if에서 확인하는 것은 (ncol, nrow)로 확인합니다. nrow와 ncol의 위치가 뒤바껴서 생긴 에러였던것 같습니다. 

질문 아래에 있는 코드는 정상적으로 작동하는 코드입니다. 제 컴퓨터에서는 잘 작동합니다.

0

rlarhkd9900617

윽 단순한 실수였네요 감사합니다 

채점 프로그램 미작동

0

141

2

채점기능

1

132

2

주사위 게임

0

78

1

체점기

0

125

3

기존에 윈도우 10으로 잘 써왔는데 윈도우 11로 바꾸고 나서 채점이 안됩니다.

1

169

2

스택에서 ')'을 만나는 경우

0

175

3

문제가 어디있나요?

0

146

2

변수 or 함수명

0

127

1

침몰하는 타이타닉 문제 질문입니다

0

120

1

AA.py 책점 에러

0

111

1

오늘 구매했는데 파이썬 자료구조 궁금한거 있으면 답변이 잘 될까요.

0

162

2

5.동전분배하기 문제 밑에코드도 정답이될까요?

0

170

1

아나그램 비교 코드

0

183

2

AA.PY파일 복사 후 채점 진행할때 오류 발생합니다.

0

236

2

문제 링크가있나여?

0

201

2

채점기 Time Limit Exceeded 오류 문의

1

263

2

동적계획법은 사용하는 문제

0

187

2

제 코드 좀 봐주세요

0

195

1

예외가 존재할 가능성?

0

140

1

3번이 안풀립니다

0

136

0

5번 틀림

0

154

0

오류원인?

0

136

0

리스트 선언

0

168

1

침몰하는 타이타닉(그리디) 문제 질문

0

149

1