24479 알고리즘 수업 - 깊이 우선 탐색 1 깊이 우선 탐색의 가장 기초 그런데 입력량이 많아 시간초과에 주의할 것 1. 문제 https://www.acmicpc.net/problem/24479 간단 설명 깊이 우선 탐색 방법의 가장 기초 구현 노드를 방문하면서, 방문한 순서를 기록하고 마지막에 몇번째 방문했는지 출력하는 문제 2....

2146 다리만들기 BFS를 통해서 여러 선택지 중 최단거리를 구하는 문제 https://www.acmicpc.net/problem/2146 1. 문제 간단 설명 다음과 같은 섬 3개가 있을 때, 다른 섬을 잇는 다리 하나만을 놓는다 근데, 그 다리가 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법 찾기 이런식으로 3칸 ...

9935 문자열 폭팔 문자열을 입력받다가 특정 문자열이 감지되면 문자열을 터트린다 https://www.acmicpc.net/problem/9935 1. 문제 간단 설명 문자열과 폭팔 문자열을 입력받는다 폭팔 문자열이 문자열 내에 감지되면, 폭팔 문자열 내용을 날려버리고 남은 문자열은 합쳐진다 시간 초과에 주의할 것 2. 문제 분석 ...

4963 섬의 개수 4방향 탐색이 아닌 8방향 탐색문제 대각선으로도 이동할 수 있다 https://www.acmicpc.net/problem/4963 1. 문제 간단 설명 섬의 개수를 세는 문제 기존의 2667 단지번호붙이기 문제가 4방향으로만 체크 가능했다면 이 문제는 대각선도 같은 덩어리로 판별한다 그것만 제외하면 완전 같은 문제...

16236 아기상어 최단거리 탐색 응용버전 다른사람들의 풀이를 볼때마다 어떻게 이런 생각을 하는지 대단하다는 생각이 든다 다양한 방법들을 많이 알아둬서, 언젠가 유용하게 쓸 수 있으면 좋겠다 1. 문제 간단 설명 N * N 크기의 공간에 아기상어가 움직이면서 물고기를 잡아먹는다 자신보다 작은 물고기만 먹을 수 있다 맵에 먹을 물고기가 더 이...

1926 그림 그림의 개수와 가장 큰 그림의 크기를 구하는 문제 https://www.acmicpc.net/problem/1926 1743 음식물 피하기와 같이 flood fill의 기초 문제 https://www.acmicpc.net/problem/1743 1. 문제 간단 설명 가로 세로 사이즈가 주어지고, N * M 배열에 그림의 정...

2667 단지번호 붙이기 Flood-Fill 알고리즘의 대표적인 문제, 연결된 노드의 개수와 전체 묶음의 개수를 출력하는 문제 메모리 효율을 위해 visited 배열을 사용하지 않는 방법을 사용해보았다. 1. 문제 https://www.acmicpc.net/problem/2667 간단 설명 N * N 입력을 받아, 1의 덩어리가 몇개가 ...

7576 토마토 대표적인 FloodFill, SeedFill 문제. 토마토가 완숙되기까지 며칠이 걸릴까 https://www.acmicpc.net/problem/7576 1. 문제 다음과 같은 토마토를 보관하는 M * N 칸의 상자가 있다. 토마토중에는 잘 익은것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 ...

2178 미로 탐색 가장 기본적인 BFS 경로 탐색 문제 https://www.acmicpc.net/problem/2178 문제 N X M 크기로 배열되는 미로. 미로에서 1은 이동 가능한 칸, 0은 벽 이러한 미로가 주어졌을 때, (1,1)에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소의 칸의 수를 구하는 문제 입력 첫...

1260 DFS와 BFS DFS와 BFS의 기초 문제 그래프를 DFS, BFS로 출력하기 https://www.acmicpc.net/problem/1260 문제 풀이 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램 만들기 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고,...