개발하는 고라니

14716번: 현수막 혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라. www.acmicpc.net [DFS or BFS] R x C 배열에서 방문하지 않은 각 좌표를 시작으로 1로 연결된 부분의 개수를 찾으면 되는 비교적 간단한 문제이다. 단 대각선도 이동 가능함에 주의하자. # Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int r, c; static int[][] map = new int[251][251]; static i..

3187번: 양치기 꿍 입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다. 다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다. www.acmicpc.net [DFS or BFS] 나는 DFS를 연습할 겸 DFS로 풀었다. R x C의 지도에서 벽으로 둘러쌓인 각 영역내의 늑대와 양의 개수를 찾아 전체 늑대와 양의 개수에 변화를 주었다. 지도를 입력 받을 때 전체 양의 개수와 늑대의 개수를 파악하고, 각 영역을 DFS 돌며 그 영역의 늑대와 양의 개수를 파악해 늑대 >= 양이면 전체 양에서 해당 양만큼 줄이고, 반대면 늑대를 줄인다. # Code import java.io.BufferedReader; i..

2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net [DFS] 주어진 배열에서 사이클을 찾아 답을 출력할 배열에 입력하는 것이 목표이다. 나는 기존에 좀 복잡한 방법으로 사이클을 찾고 답을 출력했더니... 시간초과가 발생하였다. 그래서 어떻게 시간을 단축시킬까 하던 도중, 한 블로그를 보고 뒤통수를 맞은 느낌이었다. 너무나 쉬운 코드로 작성한 것을 보고 성찰의 시간을 갖기로 하였다. 블로그의 링크는 하단에 기재한다. 참고한 블로그의 풀이방식은 n회 DFS를 수행하며 DFS를 돌다 다음 정점이 처음 시..

13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net [DFS or BFS] 이런 2차원 배열이 주어지는 탐색문제에서 주로 BFS만 사용했어서 이번엔 DFS로 풀어보았다. 문제의 답을 도출하는 방법은 매우 단순하다. 첫째 줄에서 출발해서 검은 칸이 아닌 상하좌우 흰색 칸을 따라 마지막 줄까지 도달할 수 있는가? static boolean DFS(int y, int x){ if(y == r) return true; visit[y][x] = true; boolean result = f..

2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net [DFS] 입력 N은 홀수로만 주어지기 때문에 중간을 (n + 1) / 2로 표현한듯 하다. int[100][2] 배열을 준비하여 int[i][0]에는 i 구슬보다 가벼운 구슬, int[i][1]에는 i 구슬보다 무거운 구슬의 개수를 저장하도록 한다. n회 반복문을 돌며 현재 구슬의 무거운 구슬의 개수 또는 가벼운 구슬의 개수가 (n + 1) / 2개 이상일 때 그 구슬은 가운데의 구슬에 들어갈 수 없다. # Code import java.io..

16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net [BFS] Time Limit Exceeded(TLE)를 높은 확률로 만날 수 있는 문제이다. 여러 가지 방식으로 문제를 풀어봤으나 매번 시간 초과... 결국 AC를 받은 것은 다음과 같은 방법이다. * 갈 수 있는 칸을 저장하는 int[][] move * 빈 공간에 대해 방문 체크 boolean[][] visit * 벽에 대해 방문 체크 boolean[][] wall * 지도 저장 int[][] map 1. 입력을 받으며 벽인 곳의 move..

13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net [BFS] 백준의 숨바꼭질 시리즈 중 4번 째 문제. 이번에는 1초 뒤 -1, +1, *2 칸으로 이동할 수 있고, end에 도착했을 때 최소 시간과 그 때의 거쳐온 과정을 나열한다. 과정을 출력하는 것은, from[]이라는 배열을 준비하고, cur정점에서 next 정점으로 n만큼의 시간을 거쳐서 갈 때, from[next] = cur arr[next] = n visit[next] =true 한다. 이렇게 저장된 from[]에서 ..

17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net [DFS + 동적 프로그래밍] 가로 세로 대각선 그림처럼 다음 파이프를 놓는 것은 현재 파이프가 어떻게 놓여져 있는지에 의존한다. 그래서 dp[n][n][3]이라는 배열을 사용했고, dp[n][n][0]은 가로로 놓여져 있을 때, dp[n][n][1]은 대각선, dp[n][n][2]는 세로로 놓여져 있을 때의 경우의 수를 나타낸다. 그리고 대각선의 경우 대각선을 나타내는 좌표 뿐 아니라, 좌측, 상측 모두 빈공간이어야 함을 명심해야한다. ..