이동가능한지 많은 것을 고려해야하는 BFS -탈주범 검거-

1. 문제

 

1953. 모의 sw 역량테스트 탈주범 검거

 

SW Expert Academy

SW Expert Academy

 

탈주범이 시작 위치에서 터널을 통해 이동할 때, 일정 시간 후에 탈주범이 존재할 수 있는 곳의 개수를 구하는 문제

 

 

2. 풀이

 

어쨌든 성실하게 하나하나 구현하면 되는 문제

 

전형적인 BFS이지만 이동할 수 있는 조건이 복잡하고 까다로워서 실수할 수도 있는 문제

 

1) map의 범위를 벗어나는 곳은 이동 불가능

 

2) map에서 0인 곳은 이동할 수 없다

 

3) 주어진 터널 방향으로만 이동 가능하다

 

map에서 1번은 4방향으로 이동 가능하고, 2번은 상,하, 3번은 좌,우,..... 7번은 상,좌로만 이동가능하다

 

이에 따른 델타배열을 따로 구성해야함

 

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

 

 

4) 방문했던 곳은 이동 불가능

 

 

5) 그리고 한가지 놓칠 수 있는 부분은..?

 

터미널끼리 연결되어있을때, 이동 가능한지를 생각해야한다.

 

예를 들어 2번과 3번이 연결되어있을때 이동가능한가??

 

 

위와 같이 되어있으면 2번에서 3번이나 3번에서 2번은 이동 불가능.. 이런 부분도 정확하게 구현해야한다

 

from collections import deque

def bfs(c,r,l,m,n,maps,d):
    
    visited = [[0]*m for _ in range(n)]

    queue = deque([(c,r,maps[r][c]-1)])

    visited[r][c] = 1

    if l == 1:
        
        return 1
    
    else:
        
        ans = 0
        
        ##l시간 동안 이동
        for _ in range(l-1):
            
            ##각 시간마다 큐의 길이만큼 BFS 탐색을 반복함
            
            for _ in range(len(queue)):
            
                x,y,dir = queue.popleft()

                for ni,nj in d[dir]:
                    
                    dx = x + ni
                    dy = y + nj

                    if dx >= 0 and dx <= m-1 and dy >= 0 and dy <= n-1 and visited[dy][dx] == 0 and maps[dy][dx] != 0:
                            
                            ##이동 불가능한 경우를 모두 고려한다
                            
                        if maps[y][x] == 1:
                            
                            if ni == 1 and nj == 0:
                                
                                if maps[dy][dx] in [2,4,5]:
                                    
                                    continue
                            
                            elif ni == -1 and nj == 0:
                                
                                if maps[dy][dx] in [2,6,7]:
                                    
                                    continue
                            
                            elif ni == 0 and nj == 1:
                                
                                if maps[dy][dx] in [3,5,6]:
                                    
                                    continue
                            
                            elif ni == 0 and nj == -1:
                                
                                if maps[dy][dx] in [3,4,7]:
                                    
                                    continue
                            
                        if maps[y][x] == 2:
                            
                            if nj == -1 and ni == 0: ##올라갈때
                                
                                if maps[dy][dx] in [3,4,7]:

                                    continue

                            elif nj == 1 and ni == 0:

                                if maps[dy][dx] in [3,5,6]:

                                    continue

                        elif maps[y][x] == 3:

                            if ni == -1:

                                if maps[dy][dx] in [2,6,7]:

                                    continue


                            elif ni == 1:

                                if maps[dy][dx] in [2,4,5]:
                                    
                                    continue
                        
                        elif maps[y][x] == 4:
                            
                            if ni == 0 and nj == -1:

                                if maps[dy][dx] in [3,4,7]:

                                    continue

                            elif ni == 1 and nj == 0:

                                if maps[dy][dx] in [2,4,5]:

                                    continue

                        elif maps[y][x] == 5:

                            if ni == 1 and nj == 0:

                                if maps[dy][dx] in [2,4,5]:

                                    continue

                            elif ni == 0 and nj == 1:

                                if maps[dy][dx] in [3,5,6]:

                                    continue

                        elif maps[y][x] == 6:

                            if ni == -1 and nj == 0:

                                if maps[dy][dx] in [2,6,7]:

                                    continue

                            elif ni == 0 and nj == 1:

                                if maps[dy][dx] in [3,5,6]:

                                    continue

                        elif maps[y][x] == 7:

                            if ni == -1 and nj == 0:

                                if maps[dy][dx] in [2,6,7]:

                                    continue

                            elif ni == 0 and nj == -1:

                                if maps[dy][dx] in [3,4,7]:

                                    continue 
                        
                        queue.append((dx,dy,maps[dy][dx]-1))

                        visited[dy][dx] = visited[y][x] + 1

##이동 후에 0보다 큰 곳은 이동했다는 의미이므로, 이동한 곳을 모두 센다.
        for y in range(n):
            
            for x in range(m):
                
                if visited[y][x] > 0:
                    
                    ans += 1

        return ans




T = int(input())

for t in range(1,T+1):
    
    n,m,r,c,l = map(int,input().split())

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

##터널 타입별로 이동가능한 델타배열
    d = [[[0,1],[1,0],[0,-1],[-1,0]], [[0,1],[0,-1]], [[1,0],[-1,0]], [[0,-1],[1,0]], [[0,1],[1,0]], [[0,1],[-1,0]], [[0,-1],[-1,0]]]

    print('#'+str(t),bfs(c,r,l,m,n,maps,d))

 

6) 한가지 실수했던 부분은??

 

1번인 상하좌우 터널은 어디든지 이동가능하다고 생각했는데...

 

 

이렇게 하면 1번에서 2번이나 2번에서 1번은 이동 못하잖아..? 1번이라고 어디든지 이동가능한 것은 아니다

 

7) 마지막으로 실수했던 부분은??

 

같은 터널끼리는 당연히 이동가능하다고 생각하고 고려도 못했는데

 

아니 생각해보니까

 

 

이러면 2번에서 2번으로는 이동 못하잖아

 

이러면 maps[y][x] 값과 움직이는 방향에 따라 이동할 수 있는 곳이 달라짐

 

if maps[y][x] == 1:

    if ni == 1 and nj == 0:

        if maps[dy][dx] in [2,4,5]:

            continue

    elif ni == -1 and nj == 0:

        if maps[dy][dx] in [2,6,7]:

            continue

    elif ni == 0 and nj == 1:

        if maps[dy][dx] in [3,5,6]:

            continue

    elif ni == 0 and nj == -1:

        if maps[dy][dx] in [3,4,7]:

            continue

if maps[y][x] == 2:

    if nj == -1 and ni == 0: ##올라갈때

        if maps[dy][dx] in [3,4,7]:

            continue

    elif nj == 1 and ni == 0:

        if maps[dy][dx] in [3,5,6]:

            continue

elif maps[y][x] == 3:

    if ni == -1:

        if maps[dy][dx] in [2,6,7]:

            continue


    elif ni == 1:

        if maps[dy][dx] in [2,4,5]:

            continue

elif maps[y][x] == 4:

    if ni == 0 and nj == -1:

        if maps[dy][dx] in [3,4,7]:

            continue

    elif ni == 1 and nj == 0:

        if maps[dy][dx] in [2,4,5]:

            continue

elif maps[y][x] == 5:

    if ni == 1 and nj == 0:

        if maps[dy][dx] in [2,4,5]:

            continue

    elif ni == 0 and nj == 1:

        if maps[dy][dx] in [3,5,6]:

            continue

elif maps[y][x] == 6:

    if ni == -1 and nj == 0:

        if maps[dy][dx] in [2,6,7]:

            continue

    elif ni == 0 and nj == 1:

        if maps[dy][dx] in [3,5,6]:

            continue

elif maps[y][x] == 7:

    if ni == -1 and nj == 0:

        if maps[dy][dx] in [2,6,7]:

            continue

    elif ni == 0 and nj == -1:

        if maps[dy][dx] in [3,4,7]:

            continue

 

 

이거 좀 아쉽긴한데... 이걸 인덱싱으로 어떻게 접근하는 방식으로 바꿀려면 내 코드 구현 자체를 바꿔야할듯???

 

내 델타배열이 좀 달라가지고.. 잘 안될것 같은데

 

 

3. 되돌아보기

 

성실하게.. 주어진 조건과 요구사항대로 완전탐색.. 구현하면 된다는 마음가짐으로 A형 문제를 풀면 된다

 

타입별로 이동불가능한 조건, 중간에 실수하긴 했지만 충분히 고려 잘했고

 

주어진 시간만큼 BFS를 돌고 싶을때, 해당 시간만큼만 반복하고, 각 시간마다 큐의 길이만큼 반복하는거 이제는 기본이지

 

if l == 1:

    return 1

else:

    ans = 0

    ##l시간 동안 이동
    for _ in range(l-1):

        ##각 시간마다 큐의 길이만큼 BFS 탐색을 반복함

        for _ in range(len(queue)):

            x,y,dir = queue.popleft()