문제

입력

첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않는 검은색 격자임을 뜻한다.

출력

바깥에서 흘려준 전류가 안쪽까지 잘 전달되면 YES를 출력한다.

그렇지 않으면 NO를 출력한다.

입력 예시 1

5 6
010101
010000
011101
100011
001011

출력 예시 1

NO

입력 예시 2

8 8
11000111
01100000
00011001
11001000
10001001
10111100
01010000
00001011

출력 예시 2

YES

문제 이해

처음 시뮬레이션(방향벡터를 사용하는 유형)을 배울때 보통 DFS/BFS랑 같이 섞어서 나온다는 말을 들었다. 지금 이 문제가 바로 그런 유형이다. 보통 DFS/BFS의 연결요소를 2차원배열로 하는데(노드의 크기가 작은 경우) 거기에 방향벡터로 방향을 정하는 것만 추가되면 두 유형이 합쳐진 문제이다. 생각보다 쉽다.

중요한 것은 y값이 M-1번에 도달했을때 answer의 값을 YES로 바꾸면 된다. 그리고 실수를 하지 않으면 간단히 풀 수 있다.

코드

# 13565번 침투

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def DFS(y, x):
    global graph, visited, result
    visited[y][x] = True

    if y == (M - 1):
        result = "YES"

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

        if 0 <= new_x < N and 0 <= new_y < M and not visited[new_y][new_x] and not graph[new_y][new_x]:
            DFS(new_y, new_x)

    
# 방향벡터 동-서-남-북 순
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# 0. 입력 및 초기화
M, N = map(int, input().split()) #M세로 N가로
graph = []
visited = [[False] * N for _ in range(M)]
# 결과값을 담는 변수
result = "NO"

# 1. 연결 요소 입력
for i in range(M):
    # rstrip으로 오른쪽 공백을 삭제
    graph.append(list(map(int, input().rstrip())))

# 2. DFS호출
for i in range(N):
    if not visited[0][i] and not graph[0][i]:
        DFS(0, i) #idx

# 3. 출력
print(result)

2주전? 쯤이었다면 이 문제를 풀면서 머리가 터졌을거다. 그만큼 알고리즘과 관련된 정형화된 문제들은 연습해서 익숙해지면 풀기가 쉽다. 그리고 인생에서 많은 것이 그렇듯이 한번에 여러가지를 하는 것보다는 하나만 파는 게 훨씬 효율이 좋다. 뭐랄까 영어공부를 하면서 수학을 공부하면서 과학을 공부하는 것보다는 한놈만 패는게 낫다. 수학을 패고, 영어를 패고, 과학을 패는 것처럼. 그렇지 않으면 이런 저런 개념이 섞여서 더 잘 기억을 못하고 응용과 활용은 더더욱 못할 것이다. 이 얘기를 꺼낸 이유는 알고리즘도 똑같다는 것이다. 하나하나씩 공부하면 더 효율이 좋다.

2주전이었다면 배워야할 스킬이나, 정보가 많았을테지만, DFS 한놈만 패면서 이 문제 수준에서는 더 알아야할게 없다.