백준(BOJ) 18170 두 동전 언리미티드(Python)

 

 

문제 내용

BFS 문제였다.

두 개의 동전을 체크해야하기 때문에 visited 리스트를 2개 만들어 사용했고, 두 동전의 위치가 모두 visited에 걸리면 queue에 append하지 않는 식으로 구현했다.

그 외에도 두 동전이 모두 떨어진 경우 append하지 않았고, 한 동전이 다른 동전의 위치로 움직이는데 다른 동전이 움직이지 않는 경우 append하지 않았다. queue에는 현재 움직인 횟수와 첫번째 동전의 x,y좌표값, 두번째 동전의 x,y좌표값을 집어넣었다.

 

코드는 다음과 같다.

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

n,m=map(int,input().split())
L=[]
coin=[]
dx=[1,-1,0,0]
dy=[0,0,1,-1]
for i in range(n):
    x=list(input())
    X=[]
    for j in range(len(x)):
        if x[j]=='o':
            X.append(0)
            coin.append([i,j])
        elif x[j]=='.':
            X.append(0)
        else:
            X.append(1)
    L.append(X)
visited_1=[[0 for i in range(m)] for j in range(n)]
visited_2=[[0 for i in range(m)] for j in range(n)]
queue=deque([])
queue.append([0,coin[0][0],coin[0][1],coin[1][0],coin[1][1]])
flag=0
while queue:
    t,x1,y1,x2,y2=queue.popleft()
    visited_1[x1][y1]=1
    visited_2[x2][y2]=1
    for i in range(4):
        nx1=x1+dx[i]
        ny1=y1+dy[i]
        nx2=x2+dx[i]
        ny2=y2+dy[i]
        if (0>nx1 or nx1>=n or 0>ny1 or ny1>=m) and (0>nx2 or nx2>=n or 0>ny2 or ny2>=m):
            continue
        elif (0>nx1 or nx1>=n or 0>ny1 or ny1>=m) or (0>nx2 or nx2>=n or 0>ny2 or ny2>=m):
            print(t+1)
            flag=1
            break
        else:
            if nx1==x2 and ny1==y2 and not L[nx2][ny2] and not (visited_1[nx1][ny1] and visited_2[nx2][ny2]):
                queue.append([t+1,nx1,ny1,nx2,ny2])
            elif nx2==x1 and ny2==y1 and not L[nx1][ny1] and not (visited_1[nx1][ny1] and visited_2[nx2][ny2]):
                queue.append([t+1,nx1,ny1,nx2,ny2])
            elif (not L[nx1][ny1] and not L[nx2][ny2]) and not (visited_1[nx1][ny1] and visited_2[nx2][ny2]):
                queue.append([t+1,nx1,ny1,nx2,ny2])
            elif (not L[nx1][ny1] and L[nx2][ny2]) and not (visited_1[nx1][ny1] and visited_2[x2][y2]):
                queue.append([t+1,nx1,ny1,x2,y2])
            elif (L[nx1][ny1] and not L[nx2][ny2]) and not (visited_1[x1][y1] and visited_2[nx2][ny2]):
                queue.append([t+1,x1,y1,nx2,ny2])
    if flag:
        break
if not flag:
    print(-1)

 

조건문 분기가 좀 귀찮았던 문제.

더 깔끔하게 분기할 수 있었을 것 같지만 귀찮다.

시간 제한이 0.5초라 python으로 제출하면 시간 초과가 터질 것 같았는데, 웬일로 그냥 통과했다.