[코딩테스트][백준] 🔥 백준 2931번 "가스관" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

https://www.acmicpc.net/problem/2931

🕒 Python 풀이시간: 55분

from collections import deque

dx=[-1,0,1,0]
dy=[0,1,0,-1]

dirDict={}
dirDict['|']={0:0,2:2}
dirDict['-']={1:1,3:3}
dirDict['+']={0:0,2:2,1:1,3:3}
dirDict['1']={0:1,3:2}
dirDict['2']={3:0,2:1}
dirDict['3']={1:0,2:3}
dirDict['4']={1:2,0:3}

n,m=map(int,input().split())
board=[]
startPos=[]
endPos=[]
visitedSet=set()
for i in range(n):
    arr=list(input())
    for j in range(m):
        if arr[j]!='.':
            visitedSet.add((i,j))
        if arr[j]=='M':
            startPos=(i,j)
        elif arr[j]=='Z':
            endPos=(i,j)
    board.append(arr)

def findLostPos(board,start):
    q=deque()
    dir=-1
    for i in range(4):
        nx=start[0]+dx[i]
        ny=start[1]+dy[i]
        if nx<0 or ny<0 or nx>=n or ny>=m:
            continue
        if board[nx][ny]!='.' and board[nx][ny]!='Z':
            dir=i
            q.append((nx,ny))
            break
    while q:
        now=q.popleft()
        goDirFromNow=dirDict[board[now[0]][now[1]]][dir]
        nx=now[0]+dx[goDirFromNow]
        ny=now[1]+dy[goDirFromNow]
        if board[nx][ny]=='.':
            return (nx,ny)
        else:
            dir=goDirFromNow
            q.append((nx,ny))

def testRoute(board,start):
    visited=set()
    visited.add(start)
    q=deque()
    dir=-1
    for i in range(4):
        nx=start[0]+dx[i]
        ny=start[1]+dy[i]
        if nx<0 or ny<0 or nx>=n or ny>=m:
            continue
        if board[nx][ny]!='.' and board[nx][ny]!='Z':
            dir=i
            q.append((nx,ny))
            visited.add((nx,ny))
            break
    while q:
        now=q.popleft()
        if dir not in dirDict[board[now[0]][now[1]]]:
            return False
        goDirFromNow=dirDict[board[now[0]][now[1]]][dir]
        nx=now[0]+dx[goDirFromNow]
        ny=now[1]+dy[goDirFromNow]
        if nx<0 or ny<0 or nx>=n or ny>=m:
            return False
        elif board[nx][ny]=='.':
            return False
        elif board[nx][ny]=='Z':
            visited.add((nx,ny))
            if visited==visitedSet:
                return True
            return False
        else:
            dir=goDirFromNow
            q.append((nx,ny))
            visited.add((nx,ny))
    return False

lostPos=findLostPos(board,startPos)
visitedSet.add(lostPos)
answer=-1
for key in ('|','-','1','2','3','4','+'):
    board[lostPos[0]][lostPos[1]]=key
    if testRoute(board,startPos):
        print(lostPos[0]+1,lostPos[1]+1,key)
        break
    board[lostPos[0]][lostPos[1]]='.'

가스관 시뮬레이션: 끊어진 가스관 찾기! 🔧💨

가스관을 끊어진 곳을 찾아서 알맞게 연결하는 시뮬레이션 문제이다. 없어진 하나의 가스관의 위치와 올바른 가스관을 찾아야 한다. 이를 위해 먼저 가스관을 타고 들어갈 때의 방향과 나올 때의 방향을 map으로 정리를 해둔다.

이제 없어진 가스관을 먼저 찾는다. 없어진 가스관은 가스관을 시작 지점에서 타고 들어가면서 쭉 진행하다가 끊어진 지점이 있으면 이 지점을 반환한다.

이제 단순히 찾으면 어떤 길이 맞는지 다 끼워보면 된다. 대신 모든 가스관을 이용하는 것이 문제의 조건 중 하나이므로 미리 가스관과 시작과 끝지점을 저장해두고 있다가 나중에 가스관을 다 방문했는지 확인하면 된다. 나같은 경우는 set를 사용하여 비교하였다.

이렇게 Python으로 백준의 "가스관" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊