개발하는 고라니

14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net [BFS] BFS를 이용해서 풀었다. 일반적인 BFS와 다른 점은, 보통 BFS는 현재 정점에서 탐색할 수 있는 모든 정점을 Queue에 넣지만, 이 문제는 현재 정점에서 한 개의 정점만 큐에 넣을 수 있다. 큐에 들어갈 원소는 y좌표, x좌표 그리고 방향이다. static class Point{ int y, x, dir; public Point(int yy, int xx, int d){ y=yy; x=xx; dir = d; } } 현재 방향에 따라 다음 방향이..

16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net [BFS] 문제의 난이도는 그렇게 높진 않으나 접근하기가 까다로웠다. 각 층은 4방향을 가질 수 있고, 1~5층에 어떤 것을 넣든지 사용자의 결정이다. 사실상 브루트포스로 풀었다. 먼저 입력을 받을 때 원 방향, 90도, 180도, -90도 회전시킨 판의 모양을 저장한다. for(int i=1; i

16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net [BFS] 사람이 먼저 BFS 탐색을 하고, 그 다음 벽이 움직이는 벽 BFS가 실행된다.이 문제에서, 벽은 8턴 이후에는 맵에 없으므로(8줄이기 때문에 8턴 후 모든 벽은 사라진다) 9턴 째 까지 왔다면 탐색할 필요 없이 탈출에 성공한 것이다. 그래서 visit배열을 3차원 배열로 선언해 몇 번째 턴일 때 방문한 것인지 체크하였다. 플레이어는 상하좌우, 대각선, 제자리 이렇게 9곳을 탐색할 수 있다. 그리고 가장중요한 것은 다음과 같은 상황일 때의 처..

13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net [BFS] 정답률 25%를 과시라도 하듯 결코 쉽지않은 문제이다. 문제에 주어진 조건 중 몇 가지가 특히 어떻게 접근해야할지 난해했다. 그 중에 '빨간 구슬(R)과 파란 구슬(B)은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다.' 가 특히나 골치아팠다. static class Point{ int y, x; public Point(int yy, int xx){ y=y..

2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net [BFS] 전체적으로 스트레스를 유발하는 문제였던 것 같다. 일단 각 정점은 상하좌우로 벽을 갖을 수 있는점, 그래서 비트마스킹을 이용해야한다는 점이... 각 정점은 0~15를 갖을 수 있는데, 0 : 벽이 없음 1 : 서쪽으로 벽 2 : 북쪽으로 벽 4 : 동쪽으로 벽 8 : 남쪽으로 벽 이외의 숫자는 각 벽이 갖는 값을 더한 것이다. (예: 15는 동서남북 모두 벽으로 막힌 곳) #풀이 요약 1. 주어진 지도에 대해 방을 번호로 구분 (예: 1번방, 2..

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..

6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net [BFS] 바로 본론부터 얘기하자면, 일반적인 BFS와 다른 점이 존재한다. 바로 각 정점은 방향을 갖는다는 것이다. 여기서 방향이란 상하좌우를 의미한다. 방향이 존재하므로 배열도 3차원이 되어야한다. 예를 들어 방문했는지에 대한 체크하는 배열 visit[ ][ ][4], 각 정점에서 해당 방향으로 도착했을 때의 거울이 몇개 필요했는지에 대한 배열 mir[ ][ ][4]. 이뿐만이 아니다. 레이저와 거울의 특성을 고려해보면, 레이저를 거울에 비추었을 때..