dfs3 [BOJ] 5845번: Perimeter https://www.acmicpc.net/problem/5845 문제: 밀집이 이어지게 주어지는데 그것의 둘레의 길이를 구하라. 안에 구멍이 생기는 것은 무시한다. 해결: dfs를 가지고 해결할 수 있는데 둘레의 길이를 구해야 하므로 오른손 법칙을 프로그램에 적용시킨다고 생각하면 된다. 그래서 밀집의 좌표에서 시작하는 게 아니라 옆에서부터 벽을 짚고 간다는 느낌으로 생각해야 한다. 그리고 핵심은 바로 set이다. 왜냐면 좌표가 10^6까지 주어지는데 10^12짜리 배열은 선언 자체를 할 수 없기 때문에 set이라는 유용한 도구를 사용해서 좌표를 가지고 놀 수 있게 된다. 내가 허튼짓을 했던 것은 구멍인지 확인하는 함수를 구현하는데 대각선 포함 8방향을 다 봐야 하는데 상하좌우만 보게 해서 문제를 계속 .. 2018. 7. 27. [BOJ]2606번: 바이러스 문제 풀러가기 링크 2606번: 바이러스문제 분류가 플로이드 와샬 알고리즘으로 되어 있는데 나는 DFS로 풀었다. 플로이드 와샬을 짜본적이 아직 없고 사실 BFS 연습 문제 추천에서 나온 문제라 풀려고 한 건데 BFS보단 DFS가 더 쉬울 것 같았기 때문이다 ㅋㅋ 문제 자체는 간단한데 1번 컴퓨터에서 바이러스가 시작되서 연결이 되어 있는 모든 컴퓨터까지 감염이 되는데 그 감염되는 컴퓨터의 개수를 세라는 것이다. --> 탐색 DFS와 BFS라는 문제를 풀어 봤다면 엄청 쉽게 풀 수 있다. 사실 컨셉만 다른 거지 문제는 똑같다고 보면 된다. 코드 2018. 2. 5. [BOJ] 1260번: DFS와 BFS 문제 풀러 가기 링크! 1260번: DFS와 BFSDFS와 BFS를 실제로 구현해 볼 수 있는 아주 좋은 문제이다.DFS는 깊이 우선 탐색이여서 최대한 한 정점에서 최대한 깊게 갔다가 다시 돌아오는 작업을 반복해서 모든 정점을 탐색하는 것이고BFS는 너비 우선 탐색이여서 층 별로 있는 모든 정점을 다 돌면서 내려간다고 보면 된다.아직 내가 직접 쓴 글이 없어서 개인적으로 정말 좋다고 생각하는 블로그의 글의 링크를 걸어 놓을테니 이 쪽에 가서 자세히 공부하면 된다.DFS 설명, BFS 설명 개인적으로 DFS는 재귀함수를 이용하는 것을 좋아해서 원래는 스택을 쓰지만 나는 재귀함수로 구현했고 BFS는 스택을 이용해서 구현했다. BFS는 분리하지 않고 main함수에 적어서 가독성이 떨어질텐데... 그 점은 양해.. 2017. 11. 4. 이전 1 다음