글 읽기 - python 3 DFS방법으로도 풀리네용 (스포주의) + 예제 입력 5번 순서

77dptjd 1년 전 5

deque사용해서 BFS 방법으로 많이 푸는데 DFS방법으로도 풀려서 코드 공유해용.

밑에는 제가 풀면서 조금 이해 안 갔던 예제 5번 날짜별로 인구이동이 어떻게 되는지 적어놓은 것입니다.

-예제 5번-

10 100 20 90
80 100 60 70
70 20 30 40
50 20 100 10

------------

10 100 50 50
50 50 50 50
50 50 50 50
50 50 100 50
------------
30 66 66 50
30 66 50 50
50 50 62 50
50 62 62 62
------------
48 48 54 54
54 54 54 50
54 54 54 54
54 54 62 54

-예제 4번-

3 5 10
10 15 20
20 30 25
40 22 10

------------
20 20 20
20 20 20
40 20 10
------------
20 20 20
20 20 16
40 16 16
------------

화이팅 하세요

import sys
sys.setrecursionlimit(10**6)#재귀 깊이 늘려줌
def dfs(s,i,j):
    global sums#평균을 내기위한 각 인자값을 저장해줄 변수
    #밑에 try except 4세트 = 상하좌우에 조건에 맞는게 있으면 DFS함수 실행
    try:#try except사용한 이유: +1해줄때 IndexError: list index out of range가 발생 할 수 있어서
        if not vist[i][j+1] and b<=abs(s[i][j] - s[i][j+1]) and c>=abs(s[i][j] - s[i][j+1]):#not vist[i][j+1]은 이전에 저기를 갔었는데 또 가주면 안됨
            vist[i][j+1] = True
            sums += s[i][j+1]#인자값 더해줌
            s2.append([i,j+1])#i,j위치 저장 (나중에 평균내서 바꿔줘야해서.)
            dfs(s,i,j+1)#DFS함수 실행
    except:
        pass
    try:
        if not vist[i+1][j] and b<=abs(s[i][j] - s[i+1][j]) and c>=abs(s[i][j] - s[i+1][j]):
            vist[i+1][j] = True
            sums += s[i+1][j]
            s2.append([i+1,j])
            dfs(s,i+1,j)
    except:
        pass
    try:
        if i>0 and not vist[i-1][j] and b<=abs(s[i][j] - s[i-1][j]) and c>=abs(s[i][j] - s[i-1][j]):
            #0이상일때만 하는 이유 s[0][1] -s[-1][1]은 전혀 엉뚱한 값임
            vist[i-1][j] = True
            sums += s[i-1][j]
            s2.append([i-1,j])
            dfs(s,i-1,j)
    except:
        pass
    try:
        if j>0 and not vist[i][j-1] and b<=abs(s[i][j] - s[i][j-1]) and c>=abs(s[i][j] - s[i][j-1]):
            #위에와 같은 이유
            vist[i][j-1] = True
            sums += s[i][j-1]
            s2.append([i,j-1])
            dfs(s,i,j-1)
    except:
        pass
        
def ch(s,s2,sums):#바뀐 값으로 저장해주는 함수
    trans =sums//len(s2)#더한 인자값의 평균
    for i, j in s2:
        s[i][j] = trans#s2에 저장된 i,j값을 사용해 값변경


a,b,c = map(int,input().split())
s = [(list(map(int,input().split()))) for i in range(a)]
count=0
e = 0#상태를 나타내기 위해 설정함 DFS함수가 실행 됐는가 안 됐는가
while e !=1:#1이 기본 상태
    vist = [[False]*a for _ in range(a)]#하루가 지나면 방문기록을 초기화 해줌
    e = 1
    for i in range(a):
        for j in range(a):
            s2=[]
            sums = 0
            if not vist[i][j]:#방문하지 않았으면 DFS함수 실행
                dfs(s,i,j)
                if s2 != []:#s2에 값이 들어가있으면 
                    ch(s,s2,sums)#평군 값으로 변경
                    e = 0#작동 했음을 나타냄
    if e==0:#작동 했으면 count+=1  만약에 안 했으면 while문을 탈출하게 됨
        count+=1
print(count)#결과값 출력

tkfydtls 1년 전 0

감사합니다 적어주신 예제 4번, 5번에서 인구이동이 어떻게 진행되었는지를 봄으로써 문제 풀이에 큰 도움을 받았습니다

4%에서 틀리시는 분들은 혹시 저처럼 풀이에서 하루에 한번 이상의 인구이동이 일어나는게 아닌지 확인하시면 도움이 될 수도 있을 것 같습니다.

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

문제

문제

출처

ICPC

python 3 DFS방법으로도 풀리네용 (스포주의) + 예제 입력 5번 순서

77dptjd 1년 전 5

tkfydtls 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말