삼성 기출 24년 하반기 오전 | 미지의 공간 탈출

실제 현장에서 문제 보자마자 와 구현어렵겠군.. 생각하고 끝내 풀지 못하고 나온 문제이다...

그래도 다시 풀면서 침착하게 설계하니, 5시간 정도만에 풀었다.

 

빡구현인데, 하나 어긋나기 굉장히 쉬워서 테스트케이스 걸리는거 하나하나 확인하고나서야 풀었다.

문제 상 시간의 벽에서 움직임을 하나하나 제 대 로 설정하는게 쉽진 않닿ㅎ

📌문제

GOLD2 / 구현 / BFS

https://www.codetree.ai/ko/frequent-problems/problems/escape-unknown-space/description

삼성 코딩테스트 기출 문제 설명: 미지의 공간 탈출 | 코드트리

📌문제 분석 및 설계

아래와 같은 요소들로 설계를 했다.

아마 해당 문제를 푼 여러 코드들이 다 복잡할 것이고, 내것도 그렇다..

남의 코드 해석하는 것도 어려우니 집중해야할 바는 [산을 어떻게 셋팅하냐]만 봐도 될 것 같다.

 

산에서 이동하는 것 또한 하드코딩 방식밖에 없으니.. 깊이 보지 않아도 될듯하다 !

지금부터 나는 시간의 벽을 산이라고 명명하겠다. 

 

1. 위 그림처럼 산을 셋팅.

- 1-1 셋팅시 2를 발견하면 출발점으로 정의

2. 반복문을 통해 grid 탐색하며 최종 출구와 바닥상에서 산의 첫 꼭짓점 찾기. 

3번 예시

3. grid에서 산크기+1 만큼씩 탐색하며(산 한 면 크기가 3x3이면 4x4크기를 탐색), 산과 바닥을 연결하는 좌표 찾기 

- 3-1 동/서/남/북 별로 case나눠서 산위에서의 좌표 계산

4. 산과 grid에서 bfs 함수 작성

- 4-1 산에서 이동할때 '윗면 ↔ 동/서/남/북' 과 '서↔북' 이동 조건부로 구현

5. 이상 현상 함수구현

6. 메인함수 구현

- 6-1 산에서 grid로 가는 부분 못찾으면 -1 출력

- 6-2 아니면 산에서 탈출구가는 경로와 시간 계산 후 한번에 이동

- 6-3 해당시간동안 이상현상 확산해서 만약 탈출구를 가린다면 -1

- 6-4 아니면 grid상에서 최종 탈출구로 가는 경로와 시간 계산

- 6-5 해당 시간동안 이상현상 확산시키며 만약 확산경로와 최종 탈출구로 가능 경로와 겹친다면, 해당 시간에서 멈추고 다시 bfs 탐색

 

📌소스 코드

import sys
from collections import deque
sys.stdin = open("./input.txt")
input = sys.stdin.readline
dxs,dys=[0,0,1,-1],[1,-1,0,0] #동서남북

n,m,f=map(int,input().split()) #공간한변길이, 시간의벽한변길이, 이상현상 개수
grid=[list(map(int,input().split())) for _ in range(n)]
startx,starty=None,None

#산 셋팅
mountain=[[-1]*(m*4) for _ in range(2*m)]
for i in range(5):
    if i==0: #동
        for j in range(m):
            mountain[m+j][2*m:3*m]=list(map(int,input().split()))
    elif i==1: #서
        for j in range(m):
            mountain[m+j][:m]=list(map(int,input().split()))

    elif i==2: #남
        for j in range(m):
            mountain[m+j][m:2*m]=list(map(int,input().split()))
    elif i==3: #북
        for j in range(m):
            mountain[m+j][3*m:]=list(map(int,input().split()))
    else:
        for j in range(m):
            mountain[j][m:2*m]=list(map(int,input().split()))
            if 2 in mountain[j][m:2*m]: #출발지점 찾기
                startx,starty=j,m+mountain[j][m:2*m].index(2)
fire=[]
for i in range(f):
    fire.append(list(map(int,input().split())))
    grid[fire[i][0]][fire[i][1]]=-1

#산이 바닥에서 맞물리는 첫 모서리 위치와 출구 좌표찾기
endx,endy,mountain_x,mountain_y=None,None,None,None
for i in range(n):
    for j in range(n):
        if grid[i][j]==4:
            endx,endy=i,j
        elif grid[i][j]==3 and mountain_y==None:
            mountain_x,mountain_y=i,j

#산,바닥 상 산에서의 탈출구 좌표 
ingridx,ingridy=2*m-1,None #3차원 상에 바닥으로 가는 탈출구 위치
for i in range(m+2):
    if 0 in grid[mountain_x-1+i][mountain_y-1:mountain_y+m+1]:
        temp=grid[mountain_x-1+i][mountain_y-1:mountain_y+m+1].index(0)
        outMountainx,outMountainy=mountain_x-1+i,mountain_y-1+temp #2차원 평면 상 산 탈출구
        if temp==0: #1
            ingridy=i-1
        elif temp==m+1: #0
            ingridy=2*m+(m-i)
        elif 0<temp<m+2 and i==0: #3
            ingridy=3*m+(m-temp)
        else: #2
            ingridy=m+temp-1
        break

def bfs(mountainis,startx,starty,endx,endy):
    if mountainis:
        visited=[[0]*(m*4) for _ in range(2*m)]
        pq=deque([(startx,starty)])
        visited[startx][starty]=1
        while pq:
            x,y=pq.popleft()
            if (x,y)==(endx,endy):
                return visited[x][y],visited
            for dx,dy in zip(dxs,dys):
                nx,ny=x+dx,y+dy
                if 0<=x<m:
                    if nx<0:
                        ny=3*m+(2*m-ny)-1 ##
                        nx=m
                    elif ny<m:
                        ny=nx
                        nx=m
                    elif ny>=2*m:
                        ny=2*m+(m-nx-1)
                        nx=m
                else:
                    if ny>=4*m:
                        ny=0
                    elif ny<0:
                        ny=(4*m)-1

                    if nx<m:
                        if ny<m:
                            nx=ny
                            ny=m
                        elif 2*m<=ny<3*m:
                            nx=m-1-(2*m-ny)
                            ny=2*m-1
                        elif ny>=3*m:
                            nx=0
                            ny=m+(m-1-(3*m-ny))

                if 0<=nx<(2*m) and 0<=ny<(m*4) and mountain[nx][ny]==0 and visited[nx][ny]==0:
                    pq.append((nx,ny))
                    visited[nx][ny]=visited[x][y]+1
        return -1,None
    else:
        visited=[[0]*n for _ in range(n)]
        pq=deque([(startx,starty)])
        visited[startx][starty]=1
        while pq:
            x,y=pq.popleft()
            if (x,y)==(endx,endy):
                return visited[x][y],visited
            for dx,dy in zip(dxs,dys):
                nx,ny=x+dx,y+dy
                if 0<=nx<n and 0<=ny<n and (grid[nx][ny]==0 or grid[nx][ny]==4) and visited[nx][ny]==0:
                    pq.append((nx,ny))
                    visited[nx][ny]=visited[x][y]+1
        return -1,None

def move_fire(day):
    check=False
    for i,(r,c,d,v) in enumerate(fire):
        if day>0 and day%v==0:
            nx,ny=r+dxs[d],c+dys[d]
            if 0<=nx<n and 0<=ny<n and (nx,ny)!=(endx,endy) and grid[nx][ny]!=1:
                grid[nx][ny]=-1
                fire[i]=[nx,ny,d,v]
            if (nx,ny)==(outMountainx,outMountainy):
                check=True
    return check



############################################################################
result=0
days=0
stop=False
if ingridy==None: #6-1
    print(-1)
else:
    t1,_=bfs(True,startx,starty,ingridx,ingridy) #6-2
    if t1==-1:
        print(-1)
    else:
        for d in range(t1): #6-3
            if move_fire(d):
                stop=True
                print(-1)
        if stop==False:
            move_fire(t1)
            days=t1
            loop=True
            while loop: #6-4
                out=False
                t2,visitedd=bfs(False,outMountainx,outMountainy,endx,endy)
                middle=0
                if t2==-1:
                    loop=False
                else:
                    for d in range(middle+t2):
                        move_fire(days+1+d)
                        for x,y,_,_ in fire:
                            if visitedd[x][y]!=0: #6-5
                                grid[x][y]
                                out=True
                        if out==True:
                            middle+=d
                            break
                if out:
                    continue
                loop=False
            if t2==-1:
                print(-1)
            else:
                print(days+t2-1)