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

1일 1PS 18일차!

📚 문제

---

골드 2

• 얼음이 녹으면 다시 못가는 것이 외판원 문제와 비슷하다.
  • 얼음이 녹음을 표시하기 위해서 visited 를 추가한다.
• Flag 를 사용해 마지막에 출력하려했지만 While 문 안에 for 문이 중첩되어있어 Break 로 바로 빠져나오지 못했다.
  • 이 같은 경우 함수로 만들어서 return 을 사용하면 깔끔하다.

💡 포인트

---

1. 사방으로 움직이며 만약 범위를 벗어나거나 얼음이 녹아있거나, 얼음이 있지만 방문한 곳은 Pass 한다.
2. 만약 얼음이 녹아있거나, 얼음이 있지만 방문한 곳이 탈출구라면 즉시 YES 를 출력한다.

💻 코드

---

from collections import deque

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
n, m = map(int, input().split())
matrix = [list(input().rstrip()) for _ in range(n)]
r1, c1 = map(int, input().split())
r2, c2 = map(int, input().split())

r1, c1, r2, c2 = r1 - 1, c1 - 1, r2 - 1, c2 - 1


def bfs():
    visited = [[False] * m for _ in range(n)]
    visited[r1][c1] = True
    q = deque()
    q.append((r1, c1))
    while q:
        x, y = q.popleft()

        for i in range(4):
            tmp_x = x + dx[i]
            tmp_y = y + dy[i]

            if tmp_x < 0 or tmp_y < 0 or tmp_x >= n or tmp_y >= m:
                continue

            if matrix[tmp_x][tmp_y] == 'X' or visited[tmp_x][tmp_y] == True:
                if tmp_x == r2 and tmp_y == c2:
                    print("YES")
                    return
                else:
                    continue

            q.append((tmp_x, tmp_y))
            visited[tmp_x][tmp_y] = True

    print("NO")


bfs()