글 읽기 - [파이썬]코드 리뷰 부탁드립니다 ㅠ

jayb100 3년 전 0

안녕하세요! DFS와 BFS를 힘겹게 학습하고 있는데 골드 레벨은 역시 어렵네요..

아래의 코드는 1이 들어갈 수 있는 모든 경우를 상정해서 각각의 경우 0의 개수를 계산해 최대값을 찾는 코드입니다.

오류를 수정하면서 코딩하다보니 파라미터가 좀 이상할 수는 있는 것 같은데 논리적으로 이상한 점을 못찾겠습니다...

제가 "특히 여기" 라고 표시해 둔 DFS부분이 이상한 것 같습니다. 제가 각 부분마다 프린트 하면서 어디가 이상하게 동작하나 봤는데 저부분에서

DFS가 작동을 안합니다.. t가 0일때만 작동하고 그 이후부터요..

제가 리턴이 있는 함수와 없는 함수가 조금 헷갈리는 상태인데 왜 안되는지를 모르겠습니다..

함수 def DFS 단계에서 파라미터 temp도 지워보고 이리저리 해봐도 안되서 아무래도 제가 개념이 안잡혀서 그런것 같아 고수분들에게 의견을 여쭙고자 올립니다. ㅠ

읽어 주셔서 감사합니다!

from sys import stdin
from itertools import combinations
from copy import deepcopy
lab = []
n,m = map(int, stdin.readline().split())
find0 = []
for i in range(n):
    lab.append(list(map(int,stdin.readline().split())))
    for j in range(m):
        if lab[i][j] == 0:
            find0.append((i,j))
visited = [[0]*m for _ in range(n)]
wall = list(combinations(find0,3))
def walls(k, lab2):
    for j in range(3):
        a, b = wall[k][j]
        lab2[a][b] = 1
    return lab2
def DFS(temp, x,y):
    visited[x][y] = 1
    dx, dy = [-1,1,0,0],[0,0,1,-1] # 사방 check
    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]
        if 0<=xx<n and 0<=yy<m and visited[xx][yy] == 0:
            if temp[xx][yy] == 0:
                temp[xx][yy] = 2
                DFS(temp, xx,yy)
mx = 0 # 최대값
for t in range(len(wall)):
    lab2 = deepcopy(lab)
    temp = walls(t,lab2)
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 2:
                DFS(temp,i,j) #    <---- 특히 여기
    total = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                total += 1
    if total > mx :
        mx = total
print(mx)

shg9411 3년 전 1

visited 배열을 벽 새로 세울 때마다 초기화해주세요.

그리고 dfs 할 때 들어가면서 체크해주세요 visited[xx][yy]

시간 많이 줄이셔야 할 것 같아요.

shg9411 3년 전 1

오늘 체감한 부분이라 말씀드리자면

deepcopy 굉장히 느리더라구요. 복사하고 싶으시면

lab2 = [lab[i][:] for i in range(n)] 와 같이 사용하세요.

jayb100 3년 전 0

정말 감사합니다! ㅠㅠ

처음에는 [:] 복사를 사용했는데 거기에서 계속 오류가 나서 deepcopy로 한번 바꿔보았습니다 ㅠ

제가 직접 해보고싶어 아이디어만 검색해보았는데 전수조사 하라고 해서 위와 같은 방법을 썼는데 너무 경우의 수가 많은가요 ?

속도를 줄이라는 말씀이 혹시 알고리즘상에서인가요?

아... visited.. 생각도 못했습니다.. 이상하게 해놓고 고치는 과정에선 저렇게 간단한게 왜 안보이는지 모르겠습니다..

답변 정말 감사드립니다 ㅠ

shg9411 3년 전 1

저 또한 combinations를 사용해서 벽 세개를 세웠습니다.

모든 경우를 확인하는게 맞을거에요.

jayb100 3년 전 0

감사합니다! 아래 다시 작성해서 통과했습니다.

그런데 추천해주신데로 deepcopy를 안썼더니 안되더라구요.. 결과가 0으로 나오는 것으로 봐서 복사가 안되나봐요 ㅠ

감사합니다!!

from sys import stdin
from itertools import combinations
from copy import deepcopy
lab = []
n,m = map(int, stdin.readline().split())
find0 = []
for i in range(n):
    lab.append(list(map(int,stdin.readline().split())))
    for j in range(m):
        if lab[i][j] == 0:
            find0.append((i,j))
wall = list(combinations(find0,3))
def walls(k, lab2):
    global visited
    visited = [[0]*m for _ in range(n)]
    for j in range(3):
        a, b = wall[k][j]
        lab2[a][b] = 1
    return lab2
def DFS(x,y):
    visited[x][y] = 1
    dx, dy = [-1,1,0,0],[0,0,1,-1] # 사방 check
    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]
        if 0<=xx<n and 0<=yy<m and visited[xx][yy] == 0:
            if temp[xx][yy] == 0:
                temp[xx][yy] = 2
                DFS(xx,yy)
mx = 0 # 최대값
for t in range(len(wall)):
    lab2 = deepcopy(lab)
    temp = walls(t,lab2)
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 2:
                DFS(i,j)
    total = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                total += 1
    if total > mx :
        mx = total
print(mx)

shg9411 3년 전 1

https://www.acmicpc.net/source/19913957 deepcopy 안 쓴 코드입니다.
어떻게 작성하셨었는지 모르겠지만요..

jayb100 3년 전 0

와.. 정말 감사드려요 이렇게까지 ㅠㅠ

저는 lab2 = lab[:] 이렇게 썼는데 제가 잘못 알고있는 건가요?

단순히 저렇게만 바꿨는데 말씀을 그렇게 알아들어서.. 저렇게 바꾸니까 결과가 0이 나오더라구요.. 예제를 바꿔가면서 해도 ㅠ

진짜 진짜 감사드려요.. 저렇게 직접 해서 올려주시기 힘든데 ㅠㅠ 감사합니다 ㅠ

shg9411 3년 전 1

1차원 리스트의 경우 그렇게 작성하시는 것이 맞은데, 2차원이다보니 행마다 복사를 진행해줘야합니다!

jayb100 3년 전 0

와... 전혀 몰랐습니다... deepcopy 보면 깊은 복사얘기밖에 못찾았어서요..

그런데 자료 입장에서 보면 그대로 복사되는 것 아닌가요? 2차원 배열이면 1차원배열처럼 똑같이 복사되는데 요소만 배열 아닌가요?

정말 감사합니다.. 그냥 계속 deepcopy 써야되는구나 했습니다 ㅎㅎ 정말 감사드려요!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[파이썬]코드 리뷰 부탁드립니다 ㅠ

jayb100 3년 전 0

shg9411 3년 전 1

shg9411 3년 전 1

jayb100 3년 전 0

shg9411 3년 전 1

jayb100 3년 전 0

shg9411 3년 전 1

jayb100 3년 전 0

shg9411 3년 전 1

jayb100 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말