컴공과고씨

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 처음 보면 탐색 방법으로 풀어야겠다는 생각이 딱 든다. bfs를 이용해서 풀어보자! 일단 이 문제의 핵심은 벽을 1번 부술 수 있다. 그래서 나는 bool destory 변수를 두어 벽을 부수고 온 탐색인지 아닌지를 구분해 주었다. tuple을 사용하여 x좌표, y좌표, count, destory 이렇게 4개의 변수를 저장하여 큐에 넣어주는 식으로 구현하였다. 또 실수하지..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 일단 문제 제목에 나와있듯이 DFS 깊이 우선 탐색과 BFS 넓이 우선탐색을 구현 해주면 되는 문제이다. DFS의 쉽게 이해하자면 먼저 쭉쭉쭉 간다고 생각하면 편하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 무슨 말이냐면 위 표에서 1번에서 16번 가는 길을 찾으려고 할 때 DFS는 어떤식으로 탐색을 하냐면 일단 최대한 16까지 ..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제를 읽었을 때 사용해야할 알고리즘이 떠오른것은 그래프 탐색이였다. 그 중 나는 넓이 우선 탐색 bfs를 선택해서 풀었다. 전체적인 풀이 방법은 배추가 있는 한 곳에 지렁이를 풀어준다. 그리고 그 지렁이가 인접해 있는 배추를 탐색하기 시작 한다. 이때 지렁이가 지나간 곳은 bool visit로 해서 방문했다는 표시를 해준다. 그리고 bfs가 끝나고 다른 배추 위치를 bfs에 넣어 지렁이를 다시 푸는데 이때 ..