격자 문제를 이해하기 위한 기본 코드 (Python)

완전탐색 문제에서 자주 등장하는 방향 탐색

 

1. 한 칸씩 움직인다는 가정 하에, 방향을 설정한다.

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

방향은 시계 방향 순서이다.

→ ↘ ↓ ↙ ← ↖ ↑ ↗ →

 

좌표는 1사분면을 기준으로 오른쪽으로 갈수록 x값이 증가, 위로 갈수록 y값이 증가한다.

그러나 격자의 경우 오른쪽으로 갈수록 x값이 증가, 아래로 갈수록 y값이 증가한다.

 

2. (0, 0)부터 (n, n)까지 움직일 2중 for문을 작성한다.

for i in range(1, n+1):
	for j in range(1, n+1):
		check_direction(i, j) # 8가지 방향 탐색 함수

python의 for문은 n+1까지 범위를 지정해놓으면 n까지 돌게 된다.

index는 0번째부터 시작하고 격자는 1부터 시작하한다.

처음 격자 데이터를 배열에 넣을 때 n+1로 만들어주었기 때문에 위와 같은 코드가 된다.

index = n 으로 맞추어준 셈이다.

 

3. 함수에서 8가지 방향 탐색하고, 탐색하면서 제한조건을 지정한다.

def check_direction(r, c):
	for i in range(8): # 8가지 방향 탐색하기 위한 for문
		nx = r + dx[i] # i번째 방향에서 현재 r 위치에서 이동 (-1, 0, 1 중에서)
		ny = c + dy[i] # i번째 방향에서 현재 c 위치에서 이동 (-1, 0, 1 중에서)
		if 0 < nx <= n and 0 < ny <= n and arr[nx][ny] == 1: # 격자 벗어나지 않도록
		# 문제에서 원하는 조건 예시 정도로만 알아둘 것. (arr[nx][ny] == 1)
			print('문제에서 원하는 것 출력')

 

4. 전체 코드

# 선언 및 입력 받기
arr = [ [0 for _ in range(n+1)] for _ in range(n+1) ]
    for i in range(1, n+1):
        nums = list(map(int, input().split()))
        for j in range(len(nums)):
            arr[i][j+1] = nums[j]

# 방향 탐색을 위한 dx, dy 이동 값
dx = [1, 1, 0, -1, -1, -1,  0,  1]
dy = [0, 1, 1,  1,  0, -1, -1, -1]

# 탐색을 위한 함수 및 제한 조건
def check_direction(r, c):
	for i in range(8):
		nx = r + dx[i]
		ny = c + dy[i]
		if 0 < nx <= n and 0 < ny <= n and arr[nx][ny] == 1:
			print('문제가 원하는 조건 출력')

# 이동을 위한 2중 for문
for i in range(1, n+1):
	for j in range(1, n+1):
		check_direction(i, j)