[Softeer][level3] 동계 테스트 시점 예측 - 파이썬(Python)

https://softeer.ai/practice/info.do?idx=1&eid=411&sw_prbl_sbms_sn=141117 

Softeer

 

문제

북위 65도. 스웨덴의 소도시 아르예플로그(Arjeplog)에 자리한 동계 테스트 센터. 겨울 내내 얼음 두께가 1M 내외로 유지되는 광할한 얼음 호수와 그냥 걷기조차 힘든 눈길을 무대로 현대자동차그룹 연구원들은 극한 환경 속에서 더 나은 차량 성능을 확보하기 위해 제동안정성, 주행안정성, ADAS 기능 등에 대한 다양한 평가를 숨가쁘게 이어가고 있다.

이 곳은 기온이 너무 추워서 아침에 출근해보면 테스트 차량들 위에 큰 눈얼음이 생겨 있다. 정상적인 테스트를 위해서는 커다란 얼음이 어느정도 녹고 난 뒤에 가능한데, 차량 마다 당일의 테스트 가능 시점을 알기 위한 예측 프로그램을 제작 중에 있다. 

예측 프로그램은 N×M (5 ≤ N, M ≤ 100)의 격자 화면 위에 눈 얼음의 모양을 작은 정사각형들이 집합되어 있는 모양으로 변환하여 위 그림과 같이 표시해 준다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 얼음은 아침이 되면 기온이 상승하여 천천히 녹는다.

그런데 화면에서 나타난 얼음의 모양은 작은 정사각형 모양의 4변 중에서 적어도 2변 이상이 외부의 공기와 접촉했을 때 정확히 한 시간 만에 녹아 없어져 버린다. 따라서 위 그림의 모양과 같은 얼음(파란으로 표시된 부분)라면 C로 표시된 모든 얼음 격자는 한 시간 후에 사라진다.

위와 같이 얼음 내부에 있는 공간은 얼음 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므로 이 공간에 접촉한 얼음 격자는 녹지 않고 C로 표시된 얼음 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면, 아래 그림에서와 같이 C로 표시된 얼음 격자들이 사라지게 된다.

격자 화면의 맨 가장자리에는 얼음이 놓이지 않는 것으로 가정한다. 입력으로 주어진 얼음이 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성해보자. 

 

 

 

 

---

💡 사고 과정

• 외부공간을 분리한다.
  격자 화면의 맨 가장자리에는 얼음이 놓이지 않는 것으로 가정하기 때문에 0,0 은 무조건 외부공기이다.
  따라서 0,0을 시작으로 방문처리 배열을 만들고, 0이거나 2이면 2로 바꿔주는 로직을 만든다. 
• 0이거나 2이면 바꿔주는 이유는 외부 공간을 분리하다가 내부 공간(0)인곳이 어느순간 외부공간과 연결되기 때문이다!!! 
  아래 그림만 봐도 내부에 있던 공간이 외부와 연결되는 순간이 생긴다.

• 얼음이 녹는건 한번에 처리해야하므로, 2중 for문을 돌리고, 1인곳의 좌표를 저장만 해둔다. 
• 전체 탐색이 끝나면 저장된 좌표들을 한번에 2로 바꿔준다. (외부공간처리)
• 얼음의 개수는 처음에 세어 놓고, 얼음의 개수를 계산하면서 0보다 작아지는 순간까지 반복하고, while문을 탈출하면 총 몇시간이 지났는지 출력해주면 된다. 

 

💻 내가 쓴 정답코드

from collections import deque
import sys
input = sys.stdin.readline


d = [[1,0],[0,1],[-1,0],[0,-1]]

def findOut():
    queue = deque()
    queue.append([0,0])
    graph[0][0] = 2
    visited =[[False]*m for _ in range(n)]
    visited[0][0] = True

    while(queue):
        r,c = queue.popleft()
        
        for i in range(4):
            dr = r+d[i][0]
            dc = c+d[i][1]

            if (0<=dr<n) and (0<=dc<m) and not visited[dr][dc]:
                if (graph[dr][dc] == 0 or graph[dr][dc] == 2):
                    graph[dr][dc] = 2 #바깥 공기 공간으로 만들어준다.
                    queue.append([dr,dc])
                    visited[dr][dc] = True

#얼음을 녹게 만드는 함수
def check(r,c):
    global now_melt
    count = 0
    for i in range(4):
        dr = r+d[i][0]
        dc = c+d[i][1]

        if (0>dr or dr>=n or 0>dc or dc>=m):
            continue
        if (graph[dr][dc] !=2):
            continue
        count+=1

    if (count >=2):
        now_melt.append([r,c])

def nowGraphState():
    for i in range(n):
        print(graph[i])

    print("------------")




n, m = map(int,input().split())

numOfIce = 0

graph = []
for _ in range(n):
    tmpList = list(map(int,input().split()))
    numOfIce += tmpList.count(1)
    graph.append(tmpList)

findOut() #초기 바깥 세팅
#nowGraphState() #체크

time = 0
while numOfIce>0:

    now_melt = []
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                check(i,j)

    numOfIce -= len(now_melt)
    for i, j in now_melt:
        graph[i][j] = 2
    
    #공기 통하게 만들기
    findOut()

    #print("남은 얼음의 개수 : ", numOfIce)
    #nowGraphState()
    time +=1



print(time)

 

 

 

 

 

 

문제 읽기 시작한 순간 스톱워치를 시작했는데 40분만에 풀었다...

 

예전이었으면 진짜 절대 못풀었을텐데

요즘 소프티어를 통해 하루하루 성장함을 느껴서 너무 뿌듯하면서 동시에

맞았습니다를 볼 때마다 자꾸 눈물이 난다

 

이번 시험이 붙던, 안붙던 최선을 다했다는점과 

예전엔 정답을 보면서 풀었던 문제들이 이제는 혼자 풀수 있게 되었다는 점 두가지 때문에라도 의미가 너무 크다.

 

하루하루가 기쁘면서 눈물은 자꾸 나와서 롤러코스터같다. 

내일 아침 시험인데 마지막까지 열심히 최선을 다해야지..🔥