[백준 11567번] 선진이의 겨울왕국(파이썬)

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

11567번: 선진이의 겨울 왕국

문제 조건이 헷갈려서

체감적으로 까다로울 수 있는 문제.

 

이 문제에서 주의할 점들.

 

1. 도착점이 이미 X일 수 있다는 점.

2. 움직일 때 추락이 가능하다는 점.

3. 출발,도착점이 같을 수 있다는 점.

 

여기서 2번이 직관적으로 와닿지 않는데요.

그냥 일반적인 탈출만 생각하면

'시작점과 도착점이 같은데

도착점이 뚫린 위치면

바로 탈출하는거 아님??'

이렇게 생각을 하기 쉽습니다.

저도 그렇게 생각하고 처음에 문제를 풀었다가

조금 헤맸습니다.

여기 문제를 읽어보면

'손상된 얼음을 다시 밟아야 추락한다'라고 되어있어서

가만히 있으면 못빠져 나가고

움직인 곳이 손상+도착점이어야지

탈출이 가능하다는 점.

#백준 11567번 선진이의 겨울왕국
from collections import deque

dx=[0,0,1,-1]
dy=[1,-1,0,0]
N,M=map(int,input().split())
room=[list(input().rstrip()) for _ in range(N)]
sx,sy=map(int,input().split())
ex,ey=map(int,input().split())
sx-=1
sy-=1
ex-=1
ey-=1
def bfs():
    visited=[[False]*M for _ in range(N)]
    visited[sx][sy]=True
    q=deque()
    q.append((sx,sy))
    while q:
        x,y=q.popleft()

        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]

            if nx<0 or nx>=N or ny<0 or ny>=M:
                continue

            if visited[nx][ny]==True:
                #이미 얼음을 깬 곳이 도착점이라면
                if nx==ex and ny==ey:
                    print("YES")
                    return
                #만약 그냥 길이라면
                else:
                    continue

            if room[nx][ny]=='X':
                #얼음 꺤 길이 도착점이라면
                if nx==ex and ny==ey:
                    print("YES")
                    return
                else:
                    continue

            q.append((nx,ny))
            visited[nx][ny]=True

    print("NO")

bfs()

 

문제의 설명이 좀 불친절하긴 한데...

문제 조건을 읽는 연습한다는 점에서 공부할 점이 있는 문제입니다.