그래프 개념과 탐색방법

안녕하세요. 지칸입니다.

삼성전자 역량 테스트에 자주 등장하는 DFS/BFS 알고리즘에 앞서 그래프의 개념에 대해서 살펴보겠습니다.

---

1) 그래프의 개념

정점과 정점들 간의 관계를 묘사하여 임의의 한 정점에서 다른 정점으로 이동이 가능한지 등의 문제가 그래프 문제입니다.

다양한 문제들에 그래프 개념이 사용되는데 흔히 2차원 좌표에서의 문제에 많이 사용됩니다.

 

- 특정 지점 A,B 사이의 최소 거리 이동

- 벽이 존재하는 미로에서 길찾기

좌표 한칸을 정점으로 보고 정점끼리의 간선이 존재하는지 문제에서 파악하여 그래프로 표현할 수 있습니다.

대표적인 그래프 문제

위 예시처럼 정점과 간선으로 문제를 그래프화하여 표현이 가능합니다.

---

2) 그래프의 요소

V : 정점

E : 간선, 두 정점을 연결하는 선

무방향 그래프 : 두 정점 사이에 쌍방통행이 가능한 연결

방향 그래프 : 두 정점 사이에 일방통행만 가능한 연결

---

3) 문제의 대입

벡준(www.acmicpc.net/) 사이트에서 알고리즘 분류로 검색하면 그래프 문제를 다양하게 볼 수 있습니다.

 

문제 2667번 단지번호붙이기

[문제 2667] <그림1>의 1이 연결된 칸의 개수와 서로 분리된 단지 개수를 맞추는 문제입니다.

위 지도의 한칸을 정점으로 보고 각 정점은 4방향으로 간선이 연결된 형태로 볼 수 있습니다.

문제 2667번 그래프화

이 문제를 풀기 위해 우리는 아래와 같은 대략적인 프로세스를 고민해 볼 수 있습니다.

1. 모든 정점에 대해 탐색을 시도할것(이중for문?), 시작 포인트가 0이면 다음 인덱스 
2. 시작 포인트가 1이면 해당 정점의 4방향을 전부 체크하여 1인 정점들 체크
3. 중복 체크를 방지하기 위해 방문하면 표시
4. 연쇄적으로 1인 정점의 체크가 이루어지고 더이상 1인 정점이 연결된 정점에 없을때 탐색 종료, 1번으로 돌아감
5. 연쇄적인 정점 체크시 정점의 개수를 저장해야하고 첫방문하는 시작포인트 1의 개수도 저장

이런 좌표형으로 표현되는 문제들은 대부분 그래프 문제이며 각 정점을 방문한다는 개념이 들어가 있습니다.

각 정점의 방문 순서에 따라 DFS/BFS 알고리즘을 구분할 수 있으며 설명은 다른 페이지에서 진행하겠습니다.

 

 

삼성 역량테스트에서 그래프 탐색 문제는 단골문제이며 문제가 상당히 정형화 되어 있다고 볼 수 있습니다.

우리는 문제를 보고 어떤 타입의 문제인지, 형태가 약간 다르다면 원래의 알고있는 형태로 되돌려 생각해야합니다.