[코딩테스트][SWEA] 🔥 SWEA 1953번 "탈주범 검거" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

🕒 Python 풀이시간: 40분

from collections import deque

def canConnect(x1,y1,x2,y2):
    type1=board[x1][y1]
    type2=board[x2][y2]
    if type1==1:
        if x1<x2:
            if type2==1 or type2==2 or type2==4 or type2==7:
                return True
        if x1>x2:
            if type2==1 or type2==2 or type2==5 or type2==6:
                return True
        if y1>y2:
            if type2==1 or type2==3 or type2==4 or type2==5:
                return True
        if y2>y1:
            if type2==1 or type2==3 or type2==6 or type2==7:
                return True
    if type1==2:
        if x1<x2:
            if type2==1 or type2==2 or type2==4 or type2==7:
                return True
        if x2<x1:
            if type2==1 or type2==2 or type2==5 or type2==6:
                return True
    if type1==3:
        if y1>y2:
            if type2==1 or type2==3 or type2==4 or type2==5:
                return True
        if y2>y1:
            if type2==1 or type2==3 or type2==6 or type2==7:
                return True
    if type1==4:
        if x1>x2:
            if type2==1 or type2==2 or type2==5 or type2==6:
                return True
        if y2>y1:
            if type2==1 or type2==3 or type2==6 or type2==7:
                return True
    if type1==5:
        if x1<x2:
            if type2==1 or type2==2 or type2==4 or type2==7:
                return True
        if y2>y1:
            if type2==1 or type2==3 or type2==6 or type2==7:
                return True
    if type1==6:
        if x1<x2:
            if type2==1 or type2==2 or type2==4 or type2==7:
                return True
        if y1>y2:
            if type2==1 or type2==3 or type2==4 or type2==5:
                return True
    if type1==7:
        if x1>x2:
            if type2==1 or type2==2 or type2==5 or type2==6:
                return True
        if y1>y2:
            if type2==1 or type2==3 or type2==4 or type2==5:
                return True
    return False

for tc in range(1,int(input())+1):
    N,M,R,C,L=map(int,input().split())
    board=[list(map(int,input().split())) for _ in range(N)]
    visited=[[-1]*M for _ in range(N)]

    q=deque()
    visited[R][C]=0
    q.append((R,C))
    while q:
        x,y=q.popleft()
        if board[x][y]==1:
            for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                nx=x+dx
                ny=y+dy
                if nx<0 or ny<0 or nx>=N or ny>=M:
                    continue
                if not (1<=board[nx][ny]<=7):
                    continue
                if visited[nx][ny]!=-1:
                    continue
                if not canConnect(x,y,nx,ny):
                    continue
                q.append((nx,ny))
                visited[nx][ny]=visited[x][y]+1
        elif board[x][y]==2:
            for dx,dy in [(-1,0),(1,0)]:
                nx=x+dx
                ny=y+dy
                if nx<0 or ny<0 or nx>=N or ny>=M:
                    continue
                if not (1<=board[nx][ny]<=7):
                    continue
                if visited[nx][ny]!=-1:
                    continue
                if not canConnect(x,y,nx,ny):
                    continue
                q.append((nx,ny))
                visited[nx][ny]=visited[x][y]+1
        elif board[x][y]==3:
            for dx,dy in [(0,-1),(0,1)]:
                nx=x+dx
                ny=y+dy
                if nx<0 or ny<0 or nx>=N or ny>=M:
                    continue
                if not (1<=board[nx][ny]<=7):
                    continue
                if visited[nx][ny]!=-1:
                    continue
                if not canConnect(x,y,nx,ny):
                    continue
                q.append((nx,ny))
                visited[nx][ny]=visited[x][y]+1
        elif board[x][y]==4:
            for dx,dy in [(-1,0),(0,1)]:
                nx=x+dx
                ny=y+dy
                if nx<0 or ny<0 or nx>=N or ny>=M:
                    continue
                if not (1<=board[nx][ny]<=7):
                    continue
                if visited[nx][ny]!=-1:
                    continue
                if not canConnect(x,y,nx,ny):
                    continue
                q.append((nx,ny))
                visited[nx][ny]=visited[x][y]+1
        elif board[x][y]==5:
            for dx,dy in [(1,0),(0,1)]:
                nx=x+dx
                ny=y+dy
                if nx<0 or ny<0 or nx>=N or ny>=M:
                    continue
                if not (1<=board[nx][ny]<=7):
                    continue
                if visited[nx][ny]!=-1:
                    continue
                if not canConnect(x,y,nx,ny):
                    continue
                q.append((nx,ny))
                visited[nx][ny]=visited[x][y]+1
        elif board[x][y]==6:
            for dx,dy in [(1,0),(0,-1)]:
                nx=x+dx
                ny=y+dy
                if nx<0 or ny<0 or nx>=N or ny>=M:
                    continue
                if not (1<=board[nx][ny]<=7):
                    continue
                if visited[nx][ny]!=-1:
                    continue
                if not canConnect(x,y,nx,ny):
                    continue
                q.append((nx,ny))
                visited[nx][ny]=visited[x][y]+1
        elif board[x][y]==7:
            for dx,dy in [(-1,0),(0,-1)]:
                nx=x+dx
                ny=y+dy
                if nx<0 or ny<0 or nx>=N or ny>=M:
                    continue
                if not (1<=board[nx][ny]<=7):
                    continue
                if visited[nx][ny]!=-1:
                    continue
                if not canConnect(x,y,nx,ny):
                    continue
                q.append((nx,ny))
                visited[nx][ny]=visited[x][y]+1
    answer=0
    for i in range(N):
        for j in range(M):
            if visited[i][j]!=-1 and visited[i][j]<L:
                answer+=1
    print("#"+str(tc)+" "+str(answer))

탈주범의 맨홀 탈출: 하수관 탐험의 비밀! 🚪💧

탈주범이 맨홀로 탈출하여 하수관을 타고 시간에 따라 이동할 수 있는 수도관의 갯수를 구하는 문제이다. 시간에 따른 갯수가 거리와 같이 늘어나므로 BFS 문제라고 생각할 수 있다.

맨홀을 시작점으로 visited를 0으로 두고 L보다 작은 visited 거리 갱신 값이 되는 갯수를 구하면 된다. 이 때 수도관이 있는 곳만 갈 수 있다. 이러한 점만 생각했다가 한번 틀릴뻔 하였다. 수도관이 있어도 연결이 되어있는 즉 현재칸에서 다음칸으로 갈 수 있는 경우에만 이동할 수 있는 것이다. 이것을 조건문으로 전부 구해주거나 해야한다. 나같은 경우는 현재의 수도관을 기준으로 x와 y값의 크기 비교를 하여 갈 수 있는 수도관을 전부 찾아서 True로 리턴해주는 함수를 구현하여 풀었다. 이는 canConnect로 구현하였다.

이렇게 Python로 SWEA의 "탈주범 검거" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊