BOJ 14546 Prison Break(Python 3)

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

문제 설명을 대충 해보자면 +오두막으로 처음 들어왔을 때는 인접한 +오두막으로만 이동할 수 있고, *오두막으로 들어왔을 때는 인접한 *오두막으로만 이동해서 탈출하는 문제이다.

전형적인 BFS 문제이고, BFS를 어떻게 구현하느냐 보다 좌표가 왼쪽 아래에서 (1,1)로 시작하고, (행,열)좌표가 아닌 (열,행)으로 뒤바뀌어져 있어서 좌표를 어떻게 입맛에 맞게 바꿀지 생각하는게 더 어려운 문제였다.

총 두 가지 방법을 사용할 수 있는데 간단한 방법은 위에서 아래로 뒤집는 것이다.

뒤집는다면 (y,x)를 (y,n-x+1)로 표현할 수 있고, 배열은 (1,1)이 아닌 (0,0)으로 시작하므로 (y-1,n-x)로 바꾼 후, 좌표를 뒤집어 (행,열)로 표현하자면 (n-x,y-1)로 나타낼 수 있다.

다른 방법은 zip을 이용하는 것이다.

예전에 What's on the grille? 이라는 문제를 풀 때 처음 알았는데, zip이라는 명령어가 배열을 합치는 것 뿐만 아니라 배열을 회전 시킬 수 도 있다는 것 이였다.

zip을 이용하여 오른쪽으로 90도 회전하여 (x-1,y-1) 을 그대로 사용하면 된다.

코드 1은 위에서 아래로 뒤집어서 푸는 방법이고, 코드 2는 zip을 이용해서 푸는 방법이다.

코드1 확인

from collections import deque
dx,dy=[0,0,1,-1],[1,-1,0,0]
for __ in range(int(input())):
    m,n,a,b,c,d=map(int,input().split())
    D=[list(map(str,[*input()])) for _ in range(n)]
    S=[[0]*m for _ in range(n)]
    sx,sy=n-b,a-1
    ex,ey=n-d,c-1
    q=deque([])
    q.append((sx,sy))
    S[sx][sy]=1
    ans=0
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<n and 0<=ny<m and D[nx][ny]==D[sx][sy] and S[nx][ny]==0:
                q.append((nx,ny))
                S[nx][ny]=1
    print(['NO','YES'][ans==1])

코드2 확인

from collections import deque
dx,dy=[0,0,1,-1],[1,-1,0,0]
for __ in range(int(input())):
    m,n,sx,sy,ex,ey=map(int,input().split())
    D=[list(map(str,[*input()])) for _ in range(n)]
    S=[[0]*n for _ in range(m)]
    q=deque()
    q.append((sx-1,sy-1))
    S[sx-1][sy-1]=1
    D=[*zip(*D[::-1])]
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<m and 0<=ny<n and D[nx][ny]==D[sx-1][sy-1] and S[nx][ny]==0:
                q.append((nx,ny))
                S[nx][ny]=1
    print(['NO','YES'][S[ex-1][ey-1]!=0])