문제 www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제를 먼저 풀고 오시는 것을 추천합니다. 이 문제의 풀이는 BFS 외에도 다양한 방법이 있을 수 있으며 제가 보여드리는 풀이는 그 중 하나입니다. 문제분석 배추흰지렁이는 인접한 다른 배추로 상하좌우 이동할 수 있습니다. 배추가 모여있는 곳은 배추흰지렁이가 한 마리만 있으면 됩니다. 배추가 군데군데 모여있어서 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있습니다. 0은 배추가 없는 땅이고, 1..

문제: 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, BFS로 탐핵한 결과를 출력하라는 문제입니다. 단, 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것부터 방문하시면 되고 더이상 방문할 수 있는 점이 없으면 종료하면 됩니다. 이번 그래프..

문제 www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제를 먼저 풀고 오시는 것을 추천합니다. 이 문제의 풀이는 DP(Dynamic Programming) 외에도 다양한 방법이 있을 수 있으며 제가 보여드리는 풀이는 그 중 하나입니다. 문제분석 정수 X에 사용할 수 있는 연산은 세가지입니다. ① 1을 뺀다. -> X가 어떤 수이든지 1을 뺄 수 있다. ② X가 2로 나누어 떨어지면, 2로 나눈다. ③ X가 3으로 나누어 떨어지면 3으로 나눈다. 실제 문제와 다르게 알아보기 쉽게 하기 위하여 1번은 1 빼기, 2번은 2로 나누기, 3번은 3으로 나누기로 재정리하였습니다. ..

문제 www.acmicpc.net/problem/1325 1번 컴퓨터 순으로 신뢰한다고 생각해보겠습니다. 그러면 5번 컴퓨터를 해킹하면 더 이상 해킹할 수 있는 컴퓨터가 없으면 ⑤ = 0 입니다. 3번 컴퓨터를 해킹하면 3을 신뢰하는 5번 컴퓨터를 해킹할 수 있으므로 ③ = 1 입니다. 1번 컴퓨터를 해킹하면 3을 해킹할 수 있고 3번 컴퓨터를 신뢰하고 5까지 해킹할 수 있습니다. 따라서, ① = 2입니다. 예제풀이 백준온라인 문제의 예제에서 나온 번호를 그래프로 그려보면 이렇게 나옵니다. 신뢰하는 관계를 방향대로 읽어가면서 해킹가능한 수를 하나씩 더하면 각 컴퓨터별로 동시에 해킹할 수 있는 개수가 나옵니다. 각 컴퓨터 번호별로 동시에 해킹할 수 있는 수는 제가 소스에서 주석처리를 풀면 확인할 수 있도록..

문제 www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제를 먼저 풀고 오신 다음에 풀이를 보시는 것을 추천드립니다. 이 문제의 풀이는 BFS/DFS 외에도 다양한 방법이 있을 수 있으며 제가 보여드리는 풀이는 그 중 하나입니다. 문제분석 1은 이동할 수 있는 칸이고, 0은 이동할 수 없는 칸입니다. (1, 1)에서 출발하여 (N, M) 위치로 이동할 때 지나야 하는 최소 칸 수를 구해야 합니다. 입력 첫째 줄에 N, M이 주어집니다. (2 0 && d[i][j - 1] == '1' && ..

문제 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제를 먼저 풀고 오신 다음에 풀이를 보시는 것을 추천드립니다. 이 문제의 풀이는 BFS 외에도 다양한 방법이 있을 수 있으며 제가 보여드리는 풀이는 그 중 하나입니다. 이 글은 BFS 알고리즘으로 2차원 배열을 사용해서 푸는 것을 알아보는 글이라서 BFS로 풀어보겠습니다. 문제분석 하루가 지나면 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들이 익습니다. 인접한 곳은 왼쪽, 오른쪽,..