[C++] 백준 11403번 경로 찾기

그래프 이론 문제.

i에서 j로 가는 경로가 있다면 인접 행렬(AdjacentMatrixGraph)로 1을 나타내고 없다면 0을 나타내면 된다.

DFS나 BFS를 이용해서 인접 행렬을 업데이트 하면 된다.

 

처음에는 자기 자신은 무조건 방문하므로 1인줄 알았는데, 두번째 테스트 케이스를 보고서 자기 자신을 돌아올 수 있는 경우에만 1이고 시작에만 자기 자신이 있다면 0이였다.

DFS, BFS는 구현만 할 줄 알면 쉽게 풀 수 있다.

 

문제풀이

그래프 이론 문제는 개념만 알고 있으면 문제를 이해하는 것은 쉬우므로 바로 코드해석을 하겠다.

사용한 STL과 변수, 그리고 BFS메서드

먼저 정점의 개수 vertex변수.

인접한 정점들의 번호를 담을 벡터 adjList,

각 정점마다 어떤 정점들을 갈 수 있는지 정보를 담을 인접행렬 check 2차원 배열을 만들었다.

 

BFS메서드는 기본적인 원리는 같다.

다만 내가 BFS에서 업데이트 하고 싶은것은 시작정점에서 어떤 정점들을 갈 수 있는지의 대한 여부이므로,

갈 수 있는 곳은 큐에 담은 후 check배열은 시작정점 기준으로 업데이트 해준다.

(현재 보고있는 정점은 그냥 어디를 갈 수 있는지에 대한 여부만 보는 것이다. check 업데이트는 시작정점 기준!)

이것을 큐가 빌 때까지 계속 반복한다.

 

메인함수

처음에 인접한 그래프에 대한 정보가 주어진다.

1이 입력됐다면 인접하다는 뜻이므로, 그래프에 해당 정점을 넣어주는 형식으로 만들었다.

그리고 1번부터 N번까지 BFS 메서드를 호출해서 check 2차원 행렬, 인접행렬 그래프를 업데이트 시키도록 만들었다.

 

후에 2중for문을 돌려서 check 배열의 상태를 출력한다.

 

그래프 탐색 문제는 실버1 문제여도 쉽게 해결할 수 있다.

 

GitHub - kimyunseok/study-record: my study-record

코드 전문은 위에서 확인 가능하다.