그래프_탐색_이론

[C++] 백준 7562번 나이트의 이동

그래프 탐색 문제. 나는 보통 배열을 쓸 때 1부터 쓰는 습관이 있는데, 이 습관이 이 문제에서는 정말 좋지 않게 작용했다. 초기화만 잘 해준다면 어렵지 않게 풀 수 있는 문제였다. 문제 풀이 문제가 대놓고 BFS (너비 우선 탐색)이라는 것을 말해주고 있다. 친절하게 그림으로도 나와있다. 각 테스트 케이스마다 좌표를 입력받고 BFS를 돌려가면서, 현재 몇 번째 탐색인지를 기록해나가며 최초로 발견한 곳에서의 번째 탐색을 찾으면 할 수 있다. 바로 코드로 살펴보자. BFS를 하기 위해 queue STL을 사용했다. testCase : 입력받는 테스트 케이스의 개수이다. widthHeight : 각 테스트 케이스마다 입력받는 가로 세로의 길이이다. board 배열 : 해당 지점을 탐색했는지 flag를 세우기..

[C++] 백준 2583번 영역 구하기

그래프 탐색 이론 문제. 백준에서 최근에 판에 색종이 올리고 남은 공간에 넓이를 구하는 문제가 있었는데, 그 문제를 푼게 도움이 많이 됐다. 어렵지 않게 풀 수 있는 문제 문제풀이 문제가 연결요소의 개수를 구하는 것을 물어보고 있다. 그리고 좌표를 알려주면서 해당 영역에 사각형이 붙여져 있다는 것을 알려준다. 좌표계를 처럼 나타내려면 조금 복잡해서, 편하게 위 아래로 뒤집은 형태로 구현해서 풀었다. 어차피 연결요소 개수는 달라지지 않을테니까. 101x101 짜리 배열을 하나 선언해서 입력받는 좌표에 따라서 해당 영역들에 이미 사각형이 있다는 것을 표시해주고, 표시되지 않은 곳에서 DFS를 해서 표시되지 않은 곳 끼리 한 영역이 되게 구현하면 된다. 좌표는 나같은 경우는 한 칸을 좌표 다음으로 보아서 (0..

[C++] 백준 2468번 안전 영역

2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net (문제가 길어서 캡쳐화면 대신 링크로 대체) 그래프 탐색 문제. 그래프 탐색에 브루트 포스(완전 탐색)를 곁들인(?) 문제이다. 문제를 이해하는 것도 어려웠고, 생각해야할 조건들도 까다로웠다. 문제풀이 일단 문제를 잘 해석해보면 연결 요소의 개수(ConnectedComponents)를 구하는 문제라는 것은 알 수 있다. 그리고 고려해야할 사항들이 있다. 물의 높이보다 낮거나 같으면 물에 잠긴다. 모든 도시가 물에 잠기지 않을 수도 있다. (연결 요소의 개수는 최소 0이..

[C++] 백준 1697번 숨바꼭질

그래프 탐색 문제인 줄 몰랐던 그래프 탐색 문제. 알고보니 모든 정점들이 서로 연결돼 있던 그래프였다는 것을 문제에서 설명해 주고 있었다. 이 사실을 질문 검색 게시판을 보다가 알게되었다. 처음 이문제를 보았을 때 수학 문제인 줄 알았다. 그래서 경우의 수를 나눠서 구현해야 하는 줄 알고 그렇게 시도했다. 결과는 틀렸습니다가 나왔다. 그래서 어떻게 풀어야 할까 고민하면서 질문 검색 게시판을 보았다. 두번째 시도 게시판에서 보니 사람들이 그래프 탐색으로 많이 풀었다는 사실을 알게되었다. "이 문제를 어떻게 그래프 탐색으로 풀까..?" 고민하던 찰나에 머리에 다익스트라와 비슷한 알고리즘이 스쳐지나갔다. 게시판 검색 안했다면 아마 생각 못하지 않았을까 생각한다. 정말 많은 문제를 풀어봐야 겠다고 생각했다. D..