문제링크 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 문제 풀이 시간의 순서대로 격자판의 상태를 나열하면 다음과 같다. 0초 : 초기상태 1초 : 초기상태와 동일(봄버맨이 아무것도 하지 않음) 2초 : 폭탄이 설치되어 있지 않은 모든 칸에 폭탄 설치 3초 : 0초에 설치되어 있던 폭탄이 폭발(폭발한 뒤의 격자판을 board_3이라고 가정) 4초 : board_3 격자판에 폭탄이 설치되어 있지 않은 모든 칸에 폭탄 설치 5초 : 2초에 설치한 폭탄이 폭발(폭발한 뒤의 격자판을 board_5라고 가정) 6초 : board_5 격..
문제 링크 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 설명 바로 이전에 풀었던 문제와 연결되는 문제다. 단지 2차원에서 3차원으로 차원이 늘어난 것이 차이점이다. 간단하게 정리를 다시 해보면 토마토 농장의 상태가 주어지고 모든 토마토가 익을 때까지 필요한 날짜를 출력해야한다. 만약 처음부터 모든 토마토가 익어있는 상태라면 0을 출력하고, 토마토가 익지 못하는 상태라면 -1을 출력해야 한다. 토마토가 익기 위해서는 익은 토마토와 인접해야만 하고 여기서 인접하다는 것은 위, 아래..
문제 링크 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 설명 토마토 농장의 현재 상태가 주어지고 모든 토마토가 익을 때까지 필요한 날짜를 출력해야 한다. 만약 모든 토마토가 익어있는 상태라면 0을 출력하고, 토마토가 익지 못하는 상태면 -1을 출력해야 한다. 토마토가 익기 위해서는 익은 토마토와 인접해야만 한다.(다른 경우는 없다.) 여기서 인접해야 한다는 말의 의미는 상, 하, 좌, 우로 인접해야 한다는 것이다.(대각선은 안된다.) 문제 풀이 bfs를 사용하여 풀이할 수 있는 문제다..
문제 링크 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 설명 주어진 미로의 (1, 1)의 위치부터 (N, M)의 위치까지 이동할 때 지나야 하는 최소의 칸 수를 구해야 한다. 문제 풀이 시작 지점에서 도착 지점으로 지나야 하는 최소의 칸 수를 출력해야 하기 때문에 이 문제는 BFS로 해결할 수 있다. 보통 최소 거리는 모두 BFS로 해결하는 것 같다. 다른 칸으로 이동할 때는 서로 인접한 칸으로만 이동이 가능하다. 즉 상, 하, 좌, 우 로만 이동이 가능한 것이다. 아래 코드에서 보면 알겠지만 그것을 조금 더 쉽게 사용하기 위해 크..
문제 링크 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 설명 트리가 주어졌을 때 트리의 루트를 1이라고 하고 각 노드의 부모를 구하는 프로그램을 작성해야 한다. 문제 풀이 입력으로 주어지는 트리를 무향 그래프로 만들어주고 1번부터 bfs를 진행한다. 이 때 parent라는 배열을 미리 만들어두고 어떤 노드를 통해 방문하였는지를 저장해주면 parent배열에는 각 노드의 부모 노드가 저장이 될 것이다. 말로만 설명하면 어려우니 그림을 통해 같이 보자. 위는 문제에서 주어진 예시이다. 예시를 통해 그래프를 그려보면 다음과 같을 것이다. 7 1 6 6 3 3 5 4 1 2..
문제 링크 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 설명 N개의 정점과 M개의 간선으로 이루어진 무향 그래프가 주어졌을 때 DFS로 방문한 정점의 순서와 BFS로 방문한 정점의 순서를 출력한다. (이 때 방문할 수 있는 정점이 여러개면 정점 번호가 작은 것부터 먼저 방문함에 주의하자.) 추가적인 부가 설명없이 코드를 보자. 코드 메모 BFS와 DFS를 공부하고 스스로 코드를 작성해보면서 공부할 수 있는 좋은 문제라고 생각된다.
문제 링크 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 설명 컴퓨터 한 대가 바이러스에 감염되면 같은 네트워크로 연결되어 있는 컴퓨터 모두가 바이러스에 감염된다고 한다. 1번 컴퓨터로 인해 감염되는 컴퓨터의 수를 출력해보자. 풀이 무향 그래프에서 시작 노드가 1이고 방문할 수 있는 노드의 개수를 세면 되는 BFS문제이다.(DFS로도 해결가능 할 것 같다.) 코드
문제 링크 1515번: 수 이어 쓰기 세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다. 세준 www.acmicpc.net 문제 설명 1부터 N까지 순서대로 써놓았는데 몇 개의 숫자가 지워진 상태다. 이 상태가 주어질 때 N의 최솟값을 구하는 문제이다. 아무것도 지워지지 않았을 수도 있다. 풀이 방법 주어지는 수의 최대 길이가 3,000자리 이고, 0~9까지 10개이기 때문에 30,000 이내에서 찾을 수 있다. 문제를 풀기 위해 두 가지 변수를 사용할 것이다. 하나는 입력 받은 문자에서 현재 보고 있는 index를 저장할 pointer변수, 다른 하나는 현재 값을 의미..
