Softeer level3 동계 테스트 시점 예측 Python

문제 링크 : https://softeer.ai/practice/info.do?idx=1&eid=411 

Softeer

정답 코드

import sys
input = sys.stdin.readline
from collections import deque
N, M = map(int, input().split())
ices = []
meltIces = []
iceBergMap = []
for r in range(N):
    tmpIce = list(map(int, input().split()))
    iceBergMap.append(tmpIce)
    for c in range(M):
        if tmpIce[c]:
            ices.append((r, c))

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

def isValid(nr, nc):
    return 0 <= nr < N and 0 <= nc < M

outSideAir = []

def checkAir():
    sr, sc = 0, 0
    tmpOutSideAir = set()
    tmpOutSideAir.add((0, 0))
    q = deque()
    q.append((sr, sc))
    V = [[0 for _ in range(M)] for _ in range(N)]
    V[sr][sc] = 1
    while q:
        r, c = q.popleft()
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if isValid(nr, nc):
                if V[nr][nc] or iceBergMap[nr][nc]:
                    continue
                V[nr][nc] = 1
                tmpOutSideAir.add((nr, nc))
                q.append((nr, nc))
    return list(tmpOutSideAir)

def melting():
    for r, c in meltIces:
        ices.remove((r, c))
        iceBergMap[r][c] = 0
    

def checkMeltIce():
    tmpMeltIce = []
    for r, c in ices:
        outCnt = 0
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if iceBergMap[nr][nc]:
                continue
            if (nr, nc) in outSideAir:
                outCnt += 1
        if outCnt > 1:
            tmpMeltIce.append((r, c))
    return tmpMeltIce

time = 0
while ices:
    time += 1
    outSideAir = checkAir()
    meltIces = checkMeltIce()
    melting()

print(time)

풀이 방식

브루트포스 알고리즘 + BFS

1. 외부 공기 확인 checkAir : BFS

2. 녹는 얼음 확인 checkMeltIce : bruteForce 브루트포스

3. 얼음 녹기

 

느낀점

소프티어 문제들은 2차원 배열 전체를 확인하는 문제가 많은 것 같다. 다시말해서 브루트포스 알고리즘을 활용하는 경우가 많다고 느껴진다.