[백준 16197번] 두 동전 - python

문제 링크

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

16197번: 두 동전

풀이 

- bfs로 풀이 

동전 두 개의 각 방문 표시 배열을 만들어서 표시해주면서 풀었는데 42% 에서 자꾸 틀렸다고. ..

from collections import deque
import sys
input= sys.stdin.readline 

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

def bfs(x1,y1, x2, y2):
    q = deque()
    q.append((x1,y1,x2,y2, 0))
    visited1 = [ [False] * m for _ in range(n)]
    visited2 = [ [False] * m for _ in range(n)]
    visited1[x1][y1] = True 
    visited2[x2][y2] = True 
    
    while q :
        x1, y1, x2, y2, cnt = q.popleft()
            
        if cnt >= 10 :
            return -1 
            
        for i in range(4):
            nx1 = x1 + dx[i]
            ny1 = y1 + dy[i]
            nx2 = x2 + dx[i]
            ny2 = y2 + dy[i]     
                
            # 둘 중에 하나만 떨어지면    
            if (not( 0<=nx1<n and 0<=ny1<m) and (0<=nx2<n and 0<=ny2<m)) or (not( 0<=nx2<n and 0<=ny2<m) and (0<=nx1<n and 0<=ny1<m)):
                return cnt + 1
            
            # 움직일 수 있으면 
            if (0<=nx1<n and 0<=ny1<m) and (0<=nx2<n and 0<=ny2<m):
                # 한개라도 방문한 곳이 아니면 
                if not visited1[nx1][ny1] or not visited2[nx2][ny2]:
                    visited1[nx1][ny1] = True 
                    visited2[nx2][ny2] = True
                    # 벽이면 움직이지 못함 
                    if graph[nx1][ny1] == '#':
                        nx1 = x1
                        ny1 = y1
                    if  graph[nx2][ny2] == '#':
                        nx2 = x2
                        ny2 = y2
                
                    q.append((nx1,ny1,nx2,ny2, cnt +1))
                
    return -1 
                    
n, m = map(int,input().split())
graph = []
for _ in range(n):
    graph.append(list(map(str,input())))

coin = []
for i in range(n):
    for j in range(m):
        if graph[i][j] == 'o':
            coin.append((i,j))
            
answer = bfs(coin[0][0], coin[0][1], coin[1][0], coin[1][1])
print(answer)

- 방문 표시가 아니라 범위를 벗어나면 continue로 처리해주니 해결되었다. 

from collections import deque
import sys
input= sys.stdin.readline 

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

def bfs(x1,y1, x2, y2):
    q = deque()
    q.append((x1,y1,x2,y2, 0))
    
    while q :
        x1, y1, x2, y2, cnt = q.popleft()
            
        # 10번보다 많이 이동해야하면 -1 리턴 
        if cnt >= 10 :
            return -1 
            
        for i in range(4):
            nx1 = x1 + dx[i]
            ny1 = y1 + dy[i]
            nx2 = x2 + dx[i]
            ny2 = y2 + dy[i]     
                
            # 둘 중에 하나만 떨어지면    
            if (not( 0<=nx1<n and 0<=ny1<m) and (0<=nx2<n and 0<=ny2<m)) or (not( 0<=nx2<n and 0<=ny2<m) and (0<=nx1<n and 0<=ny1<m)):
                return cnt + 1
            
            # 움직일 수 있으면 
            if (0<=nx1<n and 0<=ny1<m) and (0<=nx2<n and 0<=ny2<m):
                # 벽이면 움직이지 못함 
                if graph[nx1][ny1] == '#':
                    nx1 = x1
                    ny1 = y1
                if  graph[nx2][ny2] == '#':
                    nx2 = x2
                    ny2 = y2
                
                q.append((nx1,ny1,nx2,ny2, cnt +1))
            # 둘 다 범위를 벗어나면 
            else :
                continue 
                
    return -1 
                    
n, m = map(int,input().split())
graph = []
for _ in range(n):
    graph.append(list(map(str,input())))

coin = []
for i in range(n):
    for j in range(m):
        if graph[i][j] == 'o':
            coin.append((i,j))
            
answer = bfs(coin[0][0], coin[0][1], coin[1][0], coin[1][1])
print(answer)