백준 #31946 죽음의 등굣길

문제 링크

[31946 죽음의 등굣길]

문제 설명

1행 1열에서 N행 M열 까지 같은 색상의 블럭만 밟아서 이동할 수 있는지 확인하는 문제

코드

import sys
input = sys.stdin.readline
from collections import deque


def bfs():
    q = deque()
    q.append((0, 0))
    visited = [[False] * M for _ in range(N)]
    visited[0][0] = True

    while q:
        r, c = q.popleft()
        if r == N - 1 and c == M - 1:
            return True
        for k in range(8):
            for i in range(X + 1):
                for j in range(X + 1):
                    nr, nc = r + dr[k] * i, c + dc[k] * j
                    if abs(nr - r) + abs(nc - c) > X:
                        continue
                    if nr < 0 or nr >= N or nc < 0 or nc >= M:
                        continue
                    if visited[nr][nc]:
                        continue
                    if arr[nr][nc] != arr[r][c]:
                        continue
                    q.append((nr, nc))
                    visited[nr][nc] = True

    return False


N = int(input())
M = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
X = int(input())
if arr[0][0] != arr[-1][-1]:
    print("DEAD")
    exit()
dr = [-1, -1, 0, 1, 1, 1, 0, -1]
dc = [0, 1, 1, 1, 0, -1, -1, -1]
if bfs():
    print("ALIVE")
else:
    print("DEAD")

풀이

단순히 오른쪽 그리고 아래로만 이동하면 되겠지 해서 계속 틀렸었다. 8방향을 다 생각해주었어야 하는 문제! 덜렁거리지 말고 집중해서 풀자!

6월달 화이팅!