★[python_파이썬_Fail]백준_2573번_빙산_풀이

공부하는허딩크 : https://www.youtube.com/live/pqYqQL97Ohc?feature=shared

 

현재 코딩스터디중...

 

보통 실버1, 2 알고리즘 문제 위주로 풀어보는데 오늘은 골드 문제가 선택되었다.

한번도 도전할 엄두가 나지 않았지만 뭐 어차피 실버 문제들도 어려운데 한번 도전이나 해보자는 마음으로 시작했다.

 

제한시간 1시간 : 아래와 같이 고민을 했다.

"""

아래의 고민을 함수단위로 나눠서 연습

1. 동서남북 확인

2. 배열을 만들어서 확인함

1) 2개의 배열이 필요할까? 하나는 동서남북 확인 / 또 하나는 덩어리 확인

    - 돌면서 동서남북이 각 0이면 -1을 해준다.

    - 근데 이전 배열을 그대로 살리고 새로운 배열을 만들어서 확인해줘야함

    - 녹는 중에 0이 발생할 수 있음

2) melt_dfs : 동서남북 확인 => 이거 한번 돌때 시간 체크

- 일단 높이 확인 후 0이면 넘어간다.

- 0보다 크면 동서남북 확인 후 0이면 -1

- 여기서 신규 배열이 필요함 뒤에 덩어리 체크가 필요함 => deepcopy로 생성

3) check_def : 덩어리 확인

- 1년일때 그래서 한바퀴 돌아서 연결되 있음을 확인 후 2 이상임을 확인

-

3. 함수 호출을 어떻게 할까?

- 일단 while문으로 돌아야함. => 무한 반복해야함 => 단 모든 빙산이 없으면 0을 출력

"""

 

<첫번째 시도 : 방향성만 잡은채 코드 미완성>

일단 다른 스터디원들도 쉽게 풀지 못했던 것과 나도 방향성을 잡은거에 만족한다.

import sys

import copy

input = sys.stdin.readline

dirX = [0, 0, -1, 1]

dirY = [-1, 1, 0, 0]

def melt_dfs(x, y):

    height = graph[x][y]

   

    for i in range(4):

        ddx = x + dirX[i]

        ddy = y + dirY[i]

        if graph[ddx][ddy] == 0: #범위 나중에 설정

            height -= 1

    return height

def check_dfs(x, y):

    for i in range(4):

        ddx = x + dirX[i]

        ddy = y + dirY[i]

        if visited[ddx][ddy] > 0:

            check_dfs(ddx, ddy)

#1. 입력 및 초기화

N, M = map(int, input().split())

graph = [[0] for _ in range(N + 1)]

#cnt = 1

#2. graph정보 입력

for i in range(N):

    nums = list(map(int, input().split()))

    graph[i].extend(nums)

#3. 함수 호출

time = 0

while True:

    visited = copy.deepcopy(graph)

    time += 1

    """melt 확인"""

    for i in range(N):

        for j in range(M):

            if graph[i][j] == 0:

                continue

            else:

                visited[i][j] = melt_dfs(i, j)

    """check 덩어리"""

    cnt = 0

    for i in range(N):

        for j in range(M):

            if graph[i][j] == 0:

                continue

            else:

                visited[i][j] = check_dfs(i, j)

 

<두번째시도 : 런타임 에러 -> 시간초과>

sys.setrecursionlimit(10**6)을 추가해주니 런타임에러는 벗어나서 통과되길 기대했으나 시간초과가 나왔다.

이후 GhatGP한테 DFS를 유지한채 코드를 효율적으로 변경해 달라고 했으나 역시나 시간초과

import sys

import copy

sys.setrecursionlimit(10**6)

input = sys.stdin.readline

"""빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)"""

dx = [-1, 1, 0, 0]

dy = [0, 0, -1, 1]

"""빙산 녹는 함수"""

def melt(x, y):

    height = graph[x][y]

    for i in range(4):

        ddx = x + dx[i]

        ddy = y + dy[i]

        if 0 <= ddx < N and 0<= ddy < M and graph[ddx][ddy] == 0 and height > 0:

            height -= 1

    return height

"""덩어리 체크 함수"""

def check_dfs(x, y):

    global visited

    visited[x][y] = True

    for i in range(4):

        ddx = x + dx[i]

        ddy = y + dy[i]

        if 0 <= ddx < N and 0<= ddy < M and after_graph[ddx][ddy] > 0 and not visited[ddx][ddy]:

            check_dfs(ddx, ddy)

#1. 입력 및 초기화

N, M = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(N)]

#3. 함수 호출하기

"""빙산이 녹은 후 덩어리 체크"""

time = 0

while True:

    """빙산이 녹는 호출 및 녹는 함수 필요"""

    after_graph = copy.deepcopy(graph)

    time += 1

    for i in range(N):

        for j in range(M):

            if graph[i][j] == 0:

                continue

            else:

                after_graph[i][j] = melt(i, j)

       

    """빙산이 녹은 후 덩어리 체크 함수 필요"""

    visited = [[False] * M for _ in range(N)]

    cnt = 0

    for i in range(N):

        for j in range(M):

            if after_graph[i][j] == 0:

                continue

            else:

                if not visited[i][j]:

                    check_dfs(i, j)

                    cnt += 1

    graph = after_graph

    check = 0

    for i in range(N):

        for j in range(M):

            if graph[i][j] == 0:

                continue

            else:

                check += 1

       

    if cnt >= 2:

        print(time)

        break

    elif check == 0:

        print(0)

        break

 

그래서 일단 DFS로 해결하는 것은 포기했다. => 아직 BFS를 몰라서 나중을 기약하기로 다짐했다.