[Python] 백준 11567번 선진이의 겨울왕국

문제

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

입력

• 첫 번째 줄은  두 개의 정수 n, m (1 ≤ n, m ≤ 500)이 주어진다. n은 격자에서 행의 개수를 의미하고, m은 열의 개수를 의미한다.다음 줄은 두개의 정수 r1과 c1 (1 ≤ r1 ≤ n, 1 ≤ c1 ≤ m)이 주어진다. 이는 선진이의 초기위치를 나타내고, 초기위치의 빙판길의 상태는 ‘X’로 주어진다.
• 다음 줄은 두개의 정수 r2과 c2 (1 ≤ r2 ≤ n, 1 ≤ c2 ≤ m)가 주어진다. 이는 올라프가 만들어 놓은 탈출구의 위치를 나타내며, 초기 위치와 일치할 수도 있다.
• 다음 n개의 줄에는 각각 m개의 문자로 이루어진 빙판길의 초기 상태가 주어진다. (손상된 얼음이면 'X'로 표시되고, 손상되지 않은 얼음은 '.' 으로 표시된다.)

출력

• 선진이가 탈출 할 수 있다면, YES를 출력하고, 없다면 NO를 출력한다.

입력 예제

4 6
X...XX
...XX.
.X..X.
......
1 6
2 2

5 4
.X..
...X
X.X.
....
.XX.
5 3
1 1

출력 예제

YES

NO

문제 풀이

• BFS를 두 번 돌리는 문제라고 생각했는데 두 번 돌릴 경우 탐색이 끝났을 때 모두 방문처리가 되어있어 다시 돌아가는 부분을 구현할 수 없다 따라서 한 번 돌려야한다.
• 성공 조건은 두가지이다.
  • 도착지가 .일 때 : 이미 한 번 방문했어야 YES
  • 도착지가 X일 때: 도착하자마자 YES

코드

from collections import deque
# 상하좌우
dy = [-1,1,0,0]
dx = [0,0,-1,1]

n, m = map(int,input().split())
graph = []
for _ in range(n):
    graph.append(list(input()))
visited = [[0] * m for _ in range(n)]

start_y, start_x = map(int,input().split())
end_y, end_x = map(int,input().split())

# -1해서 배열 인덱스와 맞추기
start_y -= 1
start_x -= 1
end_y -= 1
end_x -= 1


def go_to_end():
    global start_y, start_x, end_y, end_x
    queue = deque()
    queue.append((start_y, start_x))
    visited[start_y][start_x] = 1

    while queue:
        y, x = queue.popleft()

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < n and 0 <= nx < m:
                # 새로 간 곳이 이미 방문한 곳이라면 도착지인지 체크
                if graph[ny][nx] == '.' and visited[ny][nx] == 1:
                    if ny == end_y and nx == end_x:
                        return 'YES'
                    else:
                        continue
                # 새로 방문한 곳이 이미 꺠져있는 얼음이라면
                elif graph[ny][nx] == 'X':
                    if ny == end_y and nx == end_x:
                        return 'YES'
                    else:
                        continue
                else:
                    visited[ny][nx] = 1
                    queue.append((ny, nx))

    return 'NO'


print(go_to_end())