그래프가 주어지는 유형

1. 노드간 연결 정보만 주어지는 유형

→  그래프 정보를 인접행렬 또는 인접리스트에 담아주세요. (아래 코드는 인접행렬)

- 노드 개수 대비 간선 수가 많으면 인접행렬, 노드 개수 대비 간선 수가 적으면 인접리스트

adj = [[False for _ in range(v)] for _ in range(v)]
for _ in range(e):
    n1, n2 = map(int, input().split())
    adj[n1][n2] = adj[n2][n1] = True

 

1260번: DFS와 BFS

 

* 아래 문제는 인접리스트로 구현해야 시간/메모리 초과가 안 나는 문제

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

 

 

 

2. 격자판이 주어지는 유형 

→ 리스트(board)에 행 별로 값을 담아주세요.

board[y][x]라고 쓰면 각 요소에 접근할 수 있으며, dy와 dx 값을 이용해 상하좌우로 이동합니다.

dy = (0, 1, 0, -1)
dx = (-1, 0, 1, 0)

board = [input() for _ in range(N)]

2178번: 미로 탐색