문제

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

코드

from collections import deque

n,m=map(int,input().split())

board=[list(input()) for _ in range(n)]

coin=[]
for i in range(n):
    for j in range(m):
        if board[i][j]=='o':
            coin.append([i,j])
dx=[-1,1,0,0]
dy=[0,0,1,-1]

def dfs(coin):
    q=deque()
    q.append([coin[0],coin[1],0])

    while q:
        c1,c2,d=q.popleft()


        if d>=10:
            return -1

        for i in range(4):
            c1x = c1[0] + dx[i]
            c1y = c1[1] + dy[i]
            c2x = c2[0] + dx[i]
            c2y = c2[1] + dy[i]

            if 0<=c1x<n and 0<=c1y<m and 0<=c2x<n and 0<=c2y<m:
                if board[c1x][c1y]=='#':
                    c1x=c1[0]
                    c1y=c1[1]
                if board[c2x][c2y]=='#':
                    c2x=c2[0]
                    c2y=c2[1]

                q.append([[c1x,c1y],[c2x,c2y],d+1])
            elif 0<=c1x<n and 0<=c1y<m:
                return d+1
            elif 0<=c2x<n and 0<=c2y<m:
                return d+1
            else:
                continue

print(dfs(coin))

• 브루트포스 - bfs 문제이다.
• 두개의 동전을 같이 움직이면서 하나만 보드판에 살려놓게하는 최단거리 찾기 문제이다.

from collections import deque

n,m=map(int,input().split())

board=[list(input()) for _ in range(n)]

coin=[]
for i in range(n):
    for j in range(m):
        if board[i][j]=='o':
            coin.append([i,j])
dx=[-1,1,0,0]
dy=[0,0,1,-1]

q=deque()
q.append([coin[0],coin[1],0])
answer=11
while q:
    c1,c2,d=q.popleft()


    if d>10:
        continue

    if (c1[0]<0 or n<=c1[0]) or (c1[1]<0 or m<=c1[1]):
        if 0<=c2[0]<n and 0<=c2[1]<m:
            answer=min(answer,d)
        continue
    if (c2[0]<0 or n<=c2[0]) or (c2[1]<0 or m<=c2[1]):
        if 0<=c1[0]<n and 0<=c1[1]<m:
            answer=min(answer,d)

        continue

    for i in range(4):
        c1x=c1[0]+dx[i]
        c1y=c1[1]+dy[i]
        c2x=c2[0]+dx[i]
        c2y=c2[1]+dy[i]

        if 0<=c1x<n and 0<=c1y<m and board[c1x][c1y] == '#':
            c1x = c1[0]
            c1y = c1[1]
        if 0<=c2x<n and 0<=c2y<m and board[c2x][c2y] == '#':
            c2x = c2[0]
            c2y = c2[1]

        q.append([[c1x,c1y],[c2x,c2y],d+1])

if answer==11:
    print(-1)
else: print(answer)

맨 처음 위의 코드와 같이 (사실 함수 선언하고 가져다 쓰는게 조금 귀찮았다.. 왜지.. ) 작성했다. 설계 구상은 같았으나 위 코드같은 경우 bfs의 특성을 못살리고 모든 경우의 수를 큐에다 집어넣고 돌리는 느낌이다. 그래서 메모리초과가 났다.

함수 선언을 안했기 때문에 return 쓰기가 굉장히 애매했다.

bfs는 너비 탐색 즉 d값이 작은 순부터 차례대로 나가기 때문에 하나만 떨어진 경우가 나오면 바로끝내도되었는데 그부분을 캐치하지 못했다.

이문제는 방문기록을 만들지 않아도 된다. 어짜피 10번이상조작하면 -1을 반환하기때문