나만의 길

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net BFS를 이용하여 구현하는 문제. 그러나, 구현방식을 생각하지 못했습니다. 뱀과 사다리를 처리하는 방법을 생각하지 못해, 풀이를 참고해서 제 방식대로 구현했습니다. 먼저, 각각의 보드판에 이동 횟수를 저장하고, 방문여부와 뱀과 사다리를 적절하게 구현하여, BFS를 구현하면 됩니다. 해당 내용은 아래에서 설명하겠습니다. ※ 고려 사항 1. 뱀, 사다리 ..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net DFS, BFS를 이용하여 구현하는 그래프 문제. 단, 기존의 그래프문제와 살짝 다른 점은 3차원 공간상에서 문제를 해결해야 합니다. 2차원에서 해결하는 토마토 문제를 잘 해결하셨다면, 해당문제를 푸는데 크게 어려움은 없을 거 같습니다. 공간을 3차원으로 만들어주고, BFS를 이용하여, 각 상하좌우위아래로 움직여주면 됩니다. ※ 고려사항 1. 3차원 입력 2. BFS 3. ..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net BFS로 구현하는 문제. 해당 위치까지 최단경로로 이동하는 문제입니다. 해당문제를 단순히 재귀로 구현할 경우, 굉장히 까다로워 집니다. 왜냐하면, 상하좌우 방향 순서에 따라 도착하는 최단 경로가 달라집니다. 이에 대한 설명은 아래에서 하겠습니다. 따라서 Queue를 이용하여 BFS를 구현한 후, 문제를 해결할 수 있습니다. 유사한 문제로 7576번 토마토 문제를 푸시면 됩니다. ※ 고려사항 1. 입출력 구현 2. BFS 구현 1..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net DFS를 통해 구현하는 문제. 해당문제와 유사한 문제가 많았기 때문에, 참고해서 푼다면 금방 풀 수 있었던 문제입니다. 단, 3 구역을 각각 처리하고, 이를 2 구역으로 나누는 부분처리만 할 수 있다면 어렵지 않게 풀 수 있었던 문제입니다. ※ 고려사항 1. 입출력 처리 2. DFS 처리 3. 정상, 색약 카운팅 1. 입출력 처리 해당 문제는 기존의 그래프문제와 살짝 입력구문이 다릅니다. ..

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 그래프 이론 중, 플로이드 - 워셜 방식으로 접근하는 문제입니다. 해당 경로까지 가는 방법이 1개라도 존재한다면, 1 그렇지 않다면 0을 출력하게 합니다. 본인은 단순히 BFS로만 접근했었고, 메모리초과로 인해 조금 더 단순하게 코드를 변형한 뒤, 구현했습니다. 그러나 플로이드 - 워셜 방식을 알고 난 뒤, 문제의 접근이 굉장히 쉬워졌습니다. 그래서 BFS, 플로이드 - 워셜 방식 2가지에 대해서 알아보려 합니다. ※ 고려사항 1. 입출력..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 알고리즘 분류 힌트가 없었다면, 접근법을 찾기 굉장히 어려웠었던 문제. BFS를 통해 접근해야 합니다. 각 위치에서의 +1, -1, x2 값을 노드로 계속해서 진행한 뒤, 해당 노드가 찾고자 하는 K값이라면, 종료시키면 됩니다. 또 해당 노드의 범위가 0에서 100,000 사이의 범위에서만 존재해야 하므로, 이 부분 역시 참고해줘서 문제를 해결하면 됩니다. ※ 고려사항 ..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 전형적인 DFS, BFS로 구현하는 문제입니다. 여기서 요구하는 것은 1번 노드에서 연결된(문제에서는 감염시키는) 노드의 총 개수를 구하는 문제와 동일합니다. 단, 1번 노드 자신은 제외하고 출력해야 하므로 최종 출력 시 주의 해야합니다. ※ 고려사항 1. 입출력처리 및 노드와 간선 배열처리 2. DFS 또는 BFS 구현 3. 최종 출력시 1번 노드 제외 1. 입출력처리 및 노드와 간선 배열처리 먼저 ..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 이 문제는 전형적인 그래프이론 문제로, DFS, BFS를 이용하여 문제를 해결할 수 있습니다. 연결 노드들의 간선을 따라 이동한 뒤, DFS나 BFS 함수를 빠져나온 횟수를 카운팅 하면 됩니다. ※ 고려사항 1. 입출력을 어떻게 받을것인가? 2. DFS나 BFS 함수 구현 3. 함수 실행 처리 1. 입출력을 어떻게 받을것인가? 먼저 방..