행렬에서 인접 셀을 찾는 알고리즘

Question

예를 들어 비 랩 어라운드 4x4 행렬을 생각해보십시오.

1 2 5 1 
5 2 5 2 
9 3 1 7 
2 9 0 3 

예를 들어, 첫 번째 행에있는 5의 이웃을 찾으려면 = 2,5,1. 두 개의 for 루프를 수행하고 if 조건을 추가하는 것보다 효율적인 솔루션이 있습니까?

Answer 1

예. 이웃을 실제로 찾아야하는 경우 그래프를 사용할 수있는 옵션이 있습니다.

그래프는 기본적으로 가장자리를 형성하는 인접 꼭지점이있는 버텍스 클래스입니다. 여기서는 2가 w/5 에지를 형성하고 1이 w/5 에지를 형성한다는 것을 볼 수 있습니다.

매우 자주 이웃을 알아야 할 필요가있는 경우 (이는 비효율적이기 때문에 그다음), 그런 다음 자신의 버텍스 클래스를 구현하여 일반 T val 변수에 값 (5)을 래핑합니다. 인접한 숫자의 해시 테이블과 각각의 거리 (이 경우 1이고, 2의 이웃을 찾아야하는 경우 해시 테이블에 add (vertex, distance)를 추가하여 이들을 할당해야 할 것임)가 있어야합니다.

나중에 이웃에 대한 해시 테이블을 반복합니다.

그러나이 간단한 배열의 경우 for 루프를 수행하고 "if 문장을 많이 사용하는"오버 헤드가별로 없습니다. 실제로 모든 방향 (4)에 대해 if (경계 확인) 만하면됩니다.

이 정보가 도움이되기를 바랍니다.