https://www.acmicpc.net/problem/4672풀이체스판이 주어졌을 때 놓을 수 있는 최대 룩 개수를 구하는 문제다. 체스판은 빈 칸은 '.', 벽은 'X'로 되어있다. 룩은 벽을 통과하여 이동할 수 없다. n-Queen 문제와 비슷하게 백트래킹을 사용하여 풀었다. 로직1. 체스판을 입력하면서 빈 칸의 수를 카운트한다. 빈 칸의 수는 답(최대 룩 개수)이 될 수 있는 최댓값이기 때문에, 추후 탐색할 때 이미 해당 값을 구한다면 탐색을 더 이상 하지 않는다.2. rook(0, 0, 0)을 호출한다. rook(int r, int c, int count)(r,c) 좌표에 룩을 놓을 수 있는지 검사한 후 놓을 수 있다면 rook(r, c+1, count+1)을 호출한다.해당 칸을 스킵하는 경우..

https://www.acmicpc.net/problem/2206풀이BFS를 사용하여 최단 경로를 구하는 문제다. 이동하는 도중에 최대 1개까지 벽을 부수고 이동할 수 있기 때문에, 처음 풀 때는 모든 벽에 대해서 1개씩 부서졌을 때 BFS를 수행했다. 하지만 시간초과가 났다. 다른 사람의 풀이를 찾아본 결과 visited 배열을 3차원으로 선언하여 벽을 부쉈을 때와 부수지 않았을 때를 따로 처리하였다.boolean[][][] visited = new boolean[n][m][2]; // [r][c][0] = 벽을 부수지 않고 이동한 경우 , [r][c][1] = 벽을 부수고 이동한 경우 BFS 수행 과정1. (0, 0) 좌표에서 시작한다. 시작하는 칸도 포함해서 카운트하기 때문에 dist는 1, des..

https://www.acmicpc.net/problem/9663문제대표적인 백트래킹 문제다.완전탐색/DFS와 비슷하지만, '정답이 될 수 없다면 다시 돌아오는 과정' = 가지치기를 한다.즉, 불필요한 경로는 끝까지 탐색하지 않는다. 백트래킹의 개념과 문제 모음 풀이import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static int n; static boolean[][] board; static int count = 0; public static void main(String[] args) throws ..

https://www.acmicpc.net/problem/7576풀이대표적인 BFS 문제다.토마토 상태를 입력받을 때 익지 않은 토마토의 개수를 미리 카운트하고, BFS를 하며 익은 토마토의 개수를 카운트한다.BFS가 종료된 후 익지 않은 토마토가 있다면 -1을 출력하고, 모두 익었다면 모두 익을 때까지의 걸린 시간을 출력한다.코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static int n, m; static int[][] map; static int[] dr = {0, 1, 0, -1}; s..

https://www.acmicpc.net/problem/4920 4920번: 테트리스 게임 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 표의 크기 N이 주어지고, 4 ≤ N ≤ 100을 만족한다. 둘째 줄부터 표에 쓰여 있는 숫자가 주어진다. 숫자는 절댓 www.acmicpc.net 풀이 5가지 조각으로 배치할 수 있는 모든 도형의 경우의 수(총 13가지)를 배열로 지정하여 풀었다. 주의할 점 - n을 입력받을 때와 NxN 표를 입력받을 때 trim()을 해주어야 한다. - 표에 쓰이는 숫자는 절댓값이 1,000,000을 넘지 않는 정수이다. 즉, 음수가 입력될 수 있으므로 초기 max값을 Integer.MIN_VALUE로 초기화한다. 코드 import java.i..

https://www.acmicpc.net/problem/15886 15886번: 내 선물을 받아줘 2 욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물()을 전달해주려고 한다. 지난 며칠간의 관찰 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다. 구사과가 있는 곳은 1×N 크기의 직 www.acmicpc.net 풀이 처음 문제를 봤을 때는 BFS 알고리즘을 생각했다. 같은 위치를 다시 방문하면 안되기 때문에 boolean[] visited 방문 배열을 사용해야겠다고 생각했다. 하지만 단순한 방문배열이 아닌, 현재 탐색 단계와 이전 탐색 단계를 구분하는 방문 배열이 필요하다. ex) EEW W EW - 인덱스가 3인 W부터 시작해서 탐색할 때 왼쪽의 EEW와 합쳐진다. 따라서 카운트하지 않는다..

https://www.acmicpc.net/problem/9079 9079번: 동전 게임 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 세 줄로 이루어지며, 한 줄에 세 개의 동전모양이 주어지는데, 각각의 동전 표시 사이에는 하나의 공백이 www.acmicpc.net 풀이 모두 같은 면이 보이도록 하는 최소 연산 횟수를 구해야 하기 때문에 BFS를 사용하였다. 또한 이미 탐색했던 상태가 나올 수 있으므로, Map map을 선언하여 (동전상태, 해당 동전상태가 나오기 위한 최소 연산 횟수)를 저장한다. 동전 상태는 다음과 같이 문자열로 저장된다. H T T H T T T H H -> HTTHTTTHH BFS 로직 1. 초기 동전상태를 큐와 Map에 추가한다..

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 풀이 모든 정점에 대해 모든정점까지의 최단거리를 구해야 하기 때문에 그래프 최단거리 알고리즘을 사용했다. 1

https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 풀이 한 정점에서 다른 정점으로 최단경로로 이동할 때 가장 먼저 거쳐야 하는 정점을 구해야 하기 때문에 그래프 최단거리 알고리즘(다익스트라)을 응용하여 풀었다. 다익스트라 알고리즘을 진행할 때, 각 엣지에 먼저 거치는 정점도 저장하기 위해 Edge 클래스에 int형 멤버변수 startV를 추가했고, 이후 PQ에 엣지를 추가할 때 이전 엣지의 startV를 세팅하여 저장하는 로직을 추가하였다. static ..

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 풀이 목표지점을 시작으로 하는 BFS를 수행하여, 각 지점까지의 최단거리를 구하면 된다. 주어진 지도는 map, 각 지점까지의 최단거리는 answerMap에 저장한다. 원래 갈 수 없는 위치는 0을 출력하고, 원래 갈 수 있는 땅 중에서 도달할 수 없는 위치는 -1을 출력하기 위해, answerMap을 모두 -1로 초기화한다음, map이 0인 위치는 0..

https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net 풀이 BFS를 사용해서 최소 이동 횟수를 구하면 된다. BFS를 수행할 때, checkWall() 메서드를 사용하여 직사각형이 이동할 위치에 벽이 있는지 체크한다. 주의할 점으로는, (1, 1)부터 시작하기 때문에 Sr, Sc, Fr, Fc를 저장할 때 -1을 해야 한다. 코드 import java.io.*; import java.util.*; public class Ma..

https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 풀이 BFS를 사용해서 출발지부터 목적지까지의 최단거리를 구하면 된다. 최단거리를 총 2번 구하는데, 검을 얻지 않는 상태와 검을 얻은 상태의 최단거리를 구하여 비교한다. 둘 중 더 작은 최단거리가 T보다 작거나 같다면 그 값을 출력하고, 그렇지 않다면 Fail을 출력한다. int bfs(int startR, int startC, int destR, int destC): (star..