[백준 2931번] 가스관(파이썬)

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

2931번: 가스관

문제를 보면 당황스럽지만

하나씩 접근해보면 괜찮은 문제.

 

주의사항을 말하면

M과 Z 둘 중

하나는 움직여야합니다.

M을 기준으로 움직인다했을때

M 근처의 파이프가 사라져서

M이 움직이지 못하는 경우가 생겨서

M이 움직이지 못합니다.

그러니 M과 Z 둘 중 하나를 움직이도록 설정해주세요.

 

움직이고 나서

끊어진 좌표가 있습니다.

그 해당 좌표가 바로 M과 Z사이를 잇는 좌표죠.

 

그 다음에는 동서남북으로 해당 좌표기준으로

어떤 트랙이 있는지 구합니다.

예를들면

해당 트렉근처로

남과 북에 길이 있다면

| 도로가 있으면 되고

동 북에 길이 있다면

2를 반환하면 됩니다.

(이 부분은 구글링으로 힌트를 얻었습니다.)

#백준 2931가스관
from collections import deque
R,C=map(int,input().split())
dx=[0,0,1,-1]
dy=[1,-1,0,0]

room=[]
start=[]
sx,sy=-1,-1
ex,ey=-1,-1
ax,ay=0,0
for i in range(R):
    tmp=input().rstrip()
    for j in range(C):
        if tmp[j]=='M':
            sx,sy=i,j
            start.append([i,j])
        elif tmp[j]=='Z':
            ex,ey=i,j
            start.append([i,j])

    room.append(tmp)
def way(q):
    global ax,ay
    while q:
        x, y, dir = q.popleft()
        nx = x + dx[dir]
        ny = y + dy[dir]
        if nx < 0 or nx >= R or ny < 0 or ny >= C:
            continue

        if room[nx][ny] == '.':
            ax=nx
            ay=ny
        if visited[nx][ny] == True:
            continue

        if room[nx][ny] == '-' and (dir == 0 or dir == 1):
            visited[nx][ny] = True
            q.append([nx, ny, dir])

        elif room[nx][ny] == '|' and (dir == 2 or dir == 3):
            visited[nx][ny] = True
            q.append([nx, ny, dir])

        elif room[nx][ny] == '1':
            visited[nx][ny] = True
            if dir == 1:
                q.append([nx, ny, 2])
            elif dir == 3:
                q.append([nx, ny, 0])

        elif room[nx][ny] == '2':
            visited[nx][ny] = True
            if dir == 2:
                q.append([nx, ny, 0])
            elif dir == 1:
                q.append([nx, ny, 3])
        elif room[nx][ny] == '3':
            visited[nx][ny] = True
            if dir == 0:
                q.append([nx, ny, 3])
            elif dir == 2:
                q.append([nx, ny, 1])
        elif room[nx][ny] == '4':
            visited[nx][ny] = True
            if dir == 0:
                q.append([nx, ny, 2])
            elif dir == 3:
                q.append([nx, ny, 1])
        elif room[nx][ny] == '+':
            q.append([nx, ny, dir])

    return x,y,dir

visited=[[False]*C for _ in range(R)]
visited[sx][sy]=True
visited[ex][ey]=True
flag=False
for s in start:
    x,y=s
    q = deque()
    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        if nx < 0 or nx >= R or ny < 0 or ny >= C:
            continue

        if room[nx][ny] == '.':
            continue
        flag=True
        if room[nx][ny] == '-' and (d == 0 or d == 1):
            visited[nx][ny] = True
            q.append([nx, ny, d])

        elif room[nx][ny] == '|' and (d == 2 or d == 3):
            visited[nx][ny] = True
            q.append([nx, ny, d])

        elif room[nx][ny] == '1':
            visited[nx][ny] = True
            if d == 1:
                q.append([nx, ny, 2])
            elif d == 3:
                q.append([nx, ny, 0])

        elif room[nx][ny] == '2':
            visited[nx][ny] = True
            if d == 2:
                q.append([nx, ny, 0])
            elif d == 1:
                q.append([nx, ny, 3])
        elif room[nx][ny] == '3':
            visited[nx][ny] = True
            if d == 0:
                q.append([nx, ny, 3])
            elif d == 2:
                q.append([nx, ny, 1])
        elif room[nx][ny] == '4':
            visited[nx][ny] = True
            if d == 0:
                q.append([nx, ny, 2])
            elif d == 3:
                q.append([nx, ny, 1])
        elif room[nx][ny] == '+':
            q.append([nx, ny, d])
        if flag:
            way(q)
            break


#끊어진 지점에서 동서남북으로 방향잡기
road=''
direct=[False]*4

for d in range(4):
    nx=ax+dx[d]
    ny=ay+dy[d]

    if nx<0 or nx>=R or ny<0 or ny>=C:
        continue

    if d==0:
        if room[nx][ny]=='-' or room[nx][ny]=='+' or room[nx][ny]=='3' or room[nx][ny]=='4':
            direct[d]=True
    elif d==1:
        if room[nx][ny]=='-' or room[nx][ny]=='+' or room[nx][ny]=='1' or room[nx][ny]=='2':
            direct[d]=True
    elif d==2:
        if room[nx][ny]=='|' or room[nx][ny]=='+' or room[nx][ny]=='2' or room[nx][ny]=='3':
            direct[d]=True
    elif d==3:
        if room[nx][ny]=='|' or room[nx][ny]=='+' or room[nx][ny]=='1' or room[nx][ny]=='4':
            direct[d]=True


if direct[0] and direct[1] and not direct[2] and not direct[3]:
    road='-'
elif not direct[0] and not direct[1] and direct[2] and direct[3]:
    road='|'

elif direct[0] and direct[2] and not direct[1] and not direct[3]:
    road='1'

elif direct[0] and direct[3] and not direct[1] and not direct[2]:
    road='2'
elif direct[1] and direct[3] and not direct[0] and not direct[2]:
    road='3'
elif direct[1] and direct[2] and not direct[3] and not direct[0]:
    road='4'
else:
    road='+'

print(ax+1,ay+1,road)

 

방향을 구하는 부분으로 생각해볼것이 있는 문제입니다.

문제가 다소 지저분하다는 의견이 많은 유형이지만

한번쯤 정리해보면 좋을 것 같습니다.