격자형 구조

행(row)과 열(column)로 이루어진 2차원의 배열이다. 문제에서는 주로 NxM의 그래프 크기가 주어지며, 값을 입력받는 형태로 출제된다.

그래프

다음은 크기가 3x3인 격자형 구조의 그래프이다. (인접 리스트 형태)

graph = [
		[1, 0, 0],
        [0, 1, 0],
        [0, 0, 1],
        ]

각 요소(값)에 대한 접근은 graph[i][j] 로 한다. 각 요소를 좌표평면 위의 점으로 생각한다면, graph[i][j]의 위치를 점(i,j)로 볼 수 있다.

그래프 입력 받기

반복되는 패턴이므로 이 틀은 외워두는게 좋다.

# 공백을 기준으로 그래프 크기를 입력
N, M = map(int, input().split())	
# 그래프 생성 후 행을 기준으로 열을 입력
graph = [] 
for i in range(N): 
	graph.append(list(map(int, input().split()))

# list comprehension 
graph = [list(map(int, input().split())) for i in range(N)]

dxdy

BFS 알고리즘이나 DFS 알고리즘에서 탐색의 기준을 정하는데 이용된다. 현재 노드에서 특정 조건을 만족하는 노드로 방문해야 하는 상황에서 주변 노드들이 조건을 만족하는지 알기 위해 탐색하는 과정을 거치게 된다. 이 과정에서 탐색의 순서를 리스트에 담아 미리 정해두는 것이다.

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

문제에서는 [상, 하, 좌, 우] 로 한 칸씩 이동하는 형태가 주로 출제된다. 리스트의 값을 적절히 변경하고 추가하여 대각선 혹은 한 칸 이상 이동하는 형태를 만들 수도 있다.

문제에서 활용되는 형태

반복문을 이용하는데, 네 방향으로 탐색하기로 하였으므로 4번 반복한다. 이 반복문 안에서 next_x, next_y, graph[next_x][next_y] 등 각각의 값에 대한 조건문을 통해 다음 노드를 방문할지 말지를 결정하면 된다.

for i in range(4):
	next_x = current_x + dx[i]
    next_y = current_y + dy[i]

다음 글에서는 dxdy를 이용하는 문제를 풀이해보겠다.