2012-11-30 10 views
2

문자 (A, B, ...) 행렬이 있다고 가정합니다. 같은 char로 채워진 모든 인접한 "영역"을 찾고 해당 "영역"에 해당하는 꼭지점이있는 그래프를 만들고 싶습니다. 그래프 꼭지점은 해당 영역에 공통 경계가있는 경우에만 연결됩니다. 예를 들어연결된 구성 요소의 그래프를 만드는 방법은 무엇입니까?

:

 
input matrix: 
A A B C 
A B B B 
C C D D 

areas: 
1(A), 2(B), 3(C), 4(C), 5(D) 

output graph (adjacency list): 

1(A) - 2(B), 4(C) 
2(B) - 1(A), 3(C), 4(C), 5(D) 
3(C) - 2(B) 
4(C) - 1(A), 2(B), 5(D) 
5(D) - 2(B), 4(C)

내 질문은 : 매트릭스 주어진 이러한 그래프를 생성하는 방법에 대해 설명합니다.

분명히 다음과 같이 할 수 있습니다.

  • 실행 BFS/DFS는 연결 구성 요소 ("지역")
  • 다시 각각의 "영역"에 대한 이웃을 찾기 위해 행렬을 스캔을 찾을 수 있습니다.

더 간단하고 효율적인 방법이 있습니까?

+0

내 접근 방식이 괜찮은 것 같습니다. –

답변

1

더 나은 해결책이 없다고 생각합니다.
일부 최적화는 문자를 int로 변환 할 수 있습니다. 그러나 이것은 큰 O 표기법의 노력을 바꾸지 않을 것입니다.

어떤 사람들은 스피드 컨테스트 우승을 위해 비트 필드에 정보를 저장하려고 할 수도 있습니다. 그러나 이것도 노력할 가치가 없으며 코드도 읽을 수 없습니다.

관련 문제