[백준 1580] 위치 바꾸기

1. 문제

www.acmicpc.net/problem/1580

1580번: 위치 바꾸기

2. 접근 방법

구슬 탈출과 유사한 BFS 문제입니다

 

1. A와 B의 위치를 담는다

2. deque에다가 초기 위치를 담는다. + visit 체크

3. 만약 A가 B의 위치, B가 A의 위치에 있다면 ! => count 출력하고 끗

4. 3이 아니라면 다음에 갈 위치를 하나씩 확인하기

4-1. 벽인지 아닌지

4-2. 이미 들린 곳인지

4-3. A와 B가 크로스 되는지 (현재 A위치와 B위치가 스위칭 되는 상태)

4-4. A와 B가 같은 위치로 가는지

5. 4-1~4가 모두 아니라면, queue에 다시 담기 (count+=1)

6. bfs를 모두 돌았다면, -1을 출력

 

3. 코드

python

from collections import deque

def isWall(x, y):
    if x < 0 or y < 0 or x >= M or y >= N or board[y][x] == 'X':
        return True
    return False

def bfs():
    global _ax, _ay, _bx, _by, goalA, goalB
    while q:
        ax, ay, bx, by, c = q.popleft()
        if ax == _bx and ay == _by and bx == _ax and by == _ay:
            print(c)
            return

        for i in range(9):
            nax = ax + dx[i]
            nay = ay + dy[i]
            if isWall(nax, nay):
                continue

            for j in range(9):
                nbx = bx + dx[j]
                nby = by + dy[j]
                if isWall(nbx, nby):
                    continue

                if visited[nay][nax][nby][nbx]:
                    continue

                if nax == nbx and nay == nby:
                    continue

                if nax == bx and nay == by and nbx == ax and nby == ay:
                    continue

                if not visited[nay][nax][nby][nbx]:
                    q.append((nax, nay, nbx, nby, c+1))
                    visited[nay][nax][nby][nbx] = True
    print(-1)

N, M = map(int, input().split())
board = [list(input()) for _ in range(N)]
visited = [[[[False]*M for _ in range(N)] for _ in range(M)] for _ in range(N)]
dx, dy = (0, 1, 1, 1, 0, -1, -1, -1, 0), (-1, -1, 0, 1, 1, 1, 0, -1, 0)

for y in range(N):
    for x in range(M):
        if board[y][x] == 'A':
            _ax, _ay = x, y
        elif board[y][x] == 'B':
            _bx, _by = x, y

q = deque()
q.append((_ax, _ay, _bx, _by, 0))
visited[_ay][_ax][_by][_bx] = True
bfs()

4. 마치며

구슬 탈출에서 4차 행렬을 맞이하고

예전에 풀려고 시도했다가 감도 못잡고 못풀었던 이 문제가 갑자기 생각나서

시도했는데

 

역시나 같은 문제였슴다 ~!

 

화이팅 !@!@!@!@