[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 위 문제는 n * m의 맵에서 t 시간이 주어지는데 용사는 (0, 0) 지점에서 시작하여 t 시간 이내로 (n, m)까지 가야 한다. 근데 도중에 검을 획득하게 되면 벽을 무제한으로 뚫고 갈 수 있다. 이때 가장 빠르게 가는 시간을 구하고 못 가거나 t 시간 이내로 도착하지 못했을 경우 Fail을 반환하면 된다. 코드 import java.io.*; import java.util.*; pub..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 위 문제는 벽을 최소한으로 부수고 끝방까지 가는 문제이다. 먼저 (0, 0)을 제외한 모든 방은 visit에 Integer.MAX_VALUE를 준다. 그리고 다음 방에 방문 시 기존 방의 값보다 크면 일단 방에 들어간다. 그리고 그 방이 흰 방이면 q에 노드를 넣어주고 visited[nowX][nowY] = visited[xx][yy]를 해주고, 만약 검은 방일 경우 q에 노드를 넣어주고 visited[n..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 16469번: 소년 점프 첫째 줄에 미로의 행과 열의 크기를 나타내는 자연수 R과 C가 주어진다. (2 ≤ R, C ≤ 100) 다음 R줄에 걸 쳐 길이 C로 이루어진 각 줄의 미로의 정보가 공백 없이 주어진다. 숫자 0은 이동 가능한 www.acmicpc.net 문제는 다음과 같다 3명의 악당이 있고 이들은 동서남북으로 이동할 수 있다. 이때 서로 겹치는 부분에서 제일 최솟값으로 만나는 장소가 몇 시간 걸리는지 프린트하고 그 시간만큼 걸리는 장소가 몇 개인지 프린트하는 문제이다. 먼저 나의 경우 3차원 배열로 세 악당의 BFS 돌린 것을 저장하였고 예제를 돌렸을 때 다음과 같이 각각 장소에 몇 시간이 걸리는지 저장했다. 이렇게 말이다! (-1은 ..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 5558번: チーズ (Cheese) 入力は H+1 行ある．1 行目には 3 つの整数 H，W，N (1 ≦ H ≦ 1000，1 ≦ W ≦ 1000，1 ≦ N ≦ 9) がこの順に空白で区切られて書かれている．2 行目から H+1 行目までの各行には，'S'，'1', '2', ..., '9'， www.acmicpc.net 문제는 다음과 같다. 처음에 N * M 사이즈의 맵이 주어지고 최대 치즈의 단단함이 주어진다. 생쥐는 처음에 체력이 1인데 치즈를 먹을수록 체력은 올라간다. 하지만 치즈가 단단하기 때문에 같거나 덜 단단한 치즈만 먹을 수 있다. 즉, 체력 1일 때는 1의 치즈, 체력 3일 땐 1, 2, 3의 치즈만 먹을 수 있다. 그렇게 해서 치즈를 다 먹을 때까..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제는 다음과 같다. 토마토가 익기 위해선 동서남북으로 하나의 토마토가 무조건 있어야 같이 익는다. 쉽게 말하면 익은 토마토가 동서남북으로 안 익은 토마토를 하루 단위로 익게 한다. 따라서 예제를 기준으로 보면 아래와 같이 표현할 수 있다. BFS로 풀어주면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import j..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제 풀이는 다음과 같다. 5 x 7 사이즈의 맵이 있고 그 안에 삼각형 3개가 있다.(겹칠 수 있음) 그리고 3개의 삼각형의 크기를 입력받는데 0, 2 지점부터 4, 4 지점까지의 크기가 있다고 입력받는다. 이렇게 2번 더 걸쳐 총 3번을 받게 된다. 그리고 맵에서 빈 곳을 세어서 총 몇 개의 빈 곳이 있는지와 그 빈 곳의 개수를 오름차순으로 정렬하여 출력하면 된다. 코드(DFS) /..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 문제는 다음과 같다. 각 노드들이 서로 친구일 경우 이어져있다. 따라서 위의 예시처럼 친구 관계도를 정리해 보면 친구 관계도) 1번 - 2번 2번 - 1번, 3번, 4번 3번 - 2번, 4번, 5번 4번 - 2번, 3번, 5번 5번 - 3번, 4번 이렇게 되어있고 이중에서 회장 후보의 조건은 친구가 제일 많은 사람을 뽑으면 된다. 그래서 회원 점수가 몇 점인지, 몇 명이고 그에 따른 명단을 보여주면 된다...
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 이 문제는 나이트가 특정 좌표로 이동하는 데까지 몇 번 움직이는지 출력하는 건데 나이트는 다음과 같이 움직인다. static int dx[] = {2, 1, -1, -2, -2, -1, 1, 2}; static int dy[] = {1, 2, 2, 1, -1, -2, -2, -1}; 이 문제를 보니 바로 [BFS] 백준 - 16948번: 데스 나이트 Java 풀이 [공부용이기 때문에 코드가 깔끔하지 않을 수..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제는 1, 1부터 시작하여 n, m까지의 최단 거리를 BFS로 구하는 것이다. BFS를 공부한 지 얼마 안 돼 디버깅하면서 풀어보니 Queue에 지점을 추가할 때 x좌표, y좌표, 카운트를 넣어줘야 하기 때문에 클래스 하나를 만들어 큐에 넣어줬다. 그리고 여기서 내가 고민했던 것은 만약 막힌 길로 가면 어떻게 해야 하지였는데 생각보다 간단했다. 큐의 구조를 사용하니 큐에서 빼낸 좌표가 막힌 길로 가면 그냥 그거는 없어지면 된다. 그리고..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 문제는 다음과 같다. 그냥 가장 큰 음식물의 크기를 구하는 것이다. DFS로 하나하나 돌려보면서 카운팅 해주면 끝이다! 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { st..
