[Python][BFS] 동계 테스트 시점 예측 - Softeer

[문제]

 

[알고리즘]

• BFS 알고리즘이다.
• 얼음이 아닌 곳에서 BFS를 실행하여 방문 횟수로 녹을 얼음 알아내기
  • 얼음인 곳에 방문한 횟수가 2 이상이면 얼음을 녹임

 

[깨달은 점]

• 이 문제는 완벽한 아이디어 싸움이다...
• 나는 위 아이디어를 생각해내지 못하여 1. 얼음, 2. 얼음이 아닌 외부 3. 얼음이 아닌 얼음의 내부
  이렇게 탐색하려고 시도하였고, 결국엔 시간초과가 걸렸다. test case 11개중에 5개만을 맞췄다. 
• 이 아이디어를 머릿속에 입력하고, 나중에 써먹자!!!!!!!!!

 

[코드 - 출처: https://thflgg133.tistory.com/m/85]

import sys
from collections import deque

def bfs():
    queue = deque([[0,0]])  # 얼음의 가장자리 지점은 얼음이 존재하지 않으므로 0,0 부터 시작
    visited[0][0] = 1

    while queue:
        y, x = queue.popleft()
        
        for i in range(4): # 현재위치에서 상하좌우 탐색
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= ny < N and 0 <= nx < M: 
                if ice_land[ny][nx]: #  탐색하는 곳이 얼음이라면
                    visited[ny][nx] += 1 # 방문횟수 1 증가

                elif visited[ny][nx] == 0: # 탐색하는 곳이 얼음이 아니라면
                    queue.append([ny,nx]) # 그 지점도 탐색을 해야하므로 queue에 다시 넣어준다
                    visited[ny][nx] = 1 # 방문횟수를 1로 초기화

    for y in range(N):
        for x in range(M):
            if visited[y][x] >= 2: #  방문횟수가 2이상인 곳은 얼음이 2번이상 외부 공기와 접촉한 곳이므로 녹음
                ice_land[y][x] = 0


N, M = map(int, sys.stdin.readline().split())
ice_land = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# 상하좌우 설정
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
cnt = 0

while True: # ice_land 안에 얼음이 존재하지 않을 때 까지 시도
    if ice_land.count([0] * M) == N: 
        break

    visited = [[0] * M for _ in range(N)] # bfs()가 시도되기 전에 계속 방문 횟수를 계속 초기화 해줘야 한다
    bfs()
    cnt += 1
        
print(cnt)

 

[두번째 풀었을 때의 코드 - 통과] - 22/09/16

import sys

def print_2d(a):
    for i in a:
        for j in i :
            print(j, end=' ')
        print()

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

def count_ice():
    num_ice = 0
    for i in range(N):
        for j in range(M):
            if ice_area[i][j] ==1 :
                num_ice +=1
    return num_ice

def bfs(f, l):

    from collections import deque
    
    q = deque([[0, 0]])

    count_area = [[-1] * M for i in range(N)]

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

    while q : 
        i, j = q.popleft()

        for n in range(4):
            ii = i + dy[n]
            jj = j + dx[n]

            if ii < 0 or jj < 0 or ii > N-1 or jj > M-1 : 
                continue


            ## visit을 한 no ice 을 경우 continue 
            if count_area[ii][jj] != -1 : 
                ## no ice
                if ice_area[ii][jj] == 0 :
                    continue

                ## ice
                else :
                    count_area[ii][jj] +=1
            
            ## visit을 안했을 경우 
            else :
                ## no ice
                if ice_area[ii][jj] == 0 :
                    count_area[ii][jj] = 0
                    q.append([ii, jj])

                ## ice
                else : 
                    count_area[ii][jj] =1

    ## ice지우기
    for i in range(N):
        for j in range(M):
            if count_area[i][j] >= 2 :
                ice_area[i][j] = 0

ice_area = []
for i in range(N):
    ice_area.append(list(map(int, input().split())))

time = 0
while count_ice() > 0:
    bfs(0, 0)

    time+=1

print(time)