[알고리듬] #82 방향 검사

[key word] 

파이썬 실습창을 열 수 있습니다.실습창 열기

 

방향 검사(direction check)

방향 검사(direction check)는 행렬(array) 등에서 기준위치 주변에 있는 요소의 내용을 검사하는 것입니다. 테트리스, 체스, 바둑, 미로 찾기 등에서 사용되는 응용범위가 넓은 코딩기법(coding technique)입니다.

 

1. 방향 체크 데이터

기준점을 a[i][j]라 하면 4방향의 상대 위치는 다음과 같습니다.

4방향의 인덱스는 표의 숫자만큼 바뀝니다.

	3 (i-1,j+0)
2 (i+0, j-1)	(i, j)	0 (i+0, j+1)
	1 (i+1, j+0)

 

방향 번호	0	1	2	3
i의 상대위치 (di)	0	1	0	-1
j의 상대위치 (dj)	1	0	-1	0

 

표의 값을 list에 넣었습니다.

      di = [0, 1, 0, -1]

      dj = [1, 0, -1, 0]

이 2개의 list를 방향 체크 데이터(direction check data)라 합시다.

 

 

방향 data의 더 많은 예입니다.

 

2. 방향 체크 대이터 사용

빨간 별 주변 8곳에 있는 노란 네모의 개수를 헤아려 봅시다.

 

board=[[0,0,0,0,0],
       [0,0,1,0,0],
       [0,0,0,1,0],
       [0,1,1,1,0],
       [0,0,0,0,0]]
di=[0,1,1,1,0,-1,-1,-1]
dj=[1,1,0,-1,-1,-1,0,1]
i,j=2,2
n=0
for k in range(8):
    n+=board[i+di[k]][j+dj[k]]
print(n)

 

라인	설명
1 ~ 5	그림을 행렬(matrix, array, table)로 표현하였다. 이러한 행렬을 인접행렬(adjacency matrix:어제이슨시 매트릭스)라 한다. <d는 묵음>
6	방향 체크 데이터(direction check data)
7	기준 위치(2번째 줄(행), 2번째 칸(열))
8	노란 점의 개수
9	8방향 조사. dir은 방향을 의미한다.
10	i( 행의 변위 값(di), j에 열의 변위 값(dj)을 더하여 체크할 위치 찾는다. 체크 위치에 있는 수(0또는 1)을 더하면 노란 점의 개수가 된다.

 

방향 체크 데이터를 사용하면 프로그램을 보다 깔끔(?)하게 작성할 수 있습니다.

충분히 이해하세요.

 

안녕!