공부용

https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net https://www.acmicpc.net/problem/1600 문제와 거의 유사한 문제인 것 같다. https://www.acmicpc.net/problem/2206 문제에서는 벽을 1개만 부술 수 있었는데, 이 문제는 벽을 k개 부술 수 있다. https://pl-are.tistory.com/26 에서 풀었던 방법처럼, 3차원 배열을 k개만큼 선언해서 벽을..

https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net https://www.acmicpc.net/problem/1697 문제와 똑같이 풀면 되는데 방문했던 경로를 출력해야 하는 문제이다. 1차원 배열에 대해 BFS를 수행한다고 생각하고, -1일때, +1일때, *2일때를 조건문으로 조사하면 된다. 내가 생각한 방법은 다음과 같다. 1. 먼저 -1, +1, *2에 대해 BFS를 수행해서 최단거리가 몇초인지 구한다. (*..

https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 체스의 나이트와 같은 이동방식을 가지는 말이 있고(말은 장애물을 뛰어넘을 수 있음) 상하좌우 1칸씩 이동할 수 있는 원숭이가 있다. 원숭이는 원래는 상하좌우 1칸씩만 움직일 수 있지만 k번만큼 말처럼 이동할 수 있다. 이 때, (0,0)에서 (h-1,w-1) [w,h의 위치가 반대임을 주의] 까지의 최단경로를 구하는 문제이다. 내가 생각한 방법은 다음과 같다. 1. 최대 k번 말처..

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 여러 개의 섬에 섬과 섬을 이을 다리를 놓을 때, 여러 방법이 있겠지만 이 문제에서는 가장 거리가 짧은 한 개의 다리만을 선택해서 놓기로 한다. 이때 가장 짧은 다리의 길이를 구하는 문제이다. 나는 다음과 같은 방법으로 풀었다. 1. 먼저 한 섬에 대해 BFS를 하면서 그 섬과 인접한 바다의 좌표를 모두 저장 2. 이후 1에서 저장한 좌표를 가지고 아직 방문하지 않은 섬을 만날 때까지 BFS를 하고, ..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net BFS를 이용해서 푸는 문제이다. 이 문제는 (1) 빙산이 동시에 녹고, (2) 녹은 다음 시간이 흐르고 빙산이 나누어졌는지 확인해주어야 한다. 그래서 내가 생각한 방법은 다음과 같다. 1. 빙산을 동시에 녹인다. 2. 시간을 1년 더해준다. 3. 이후 BFS를 통해 빙산이 연결되어있는지 확인한 후, 연결되어있지 않거나 빙산이 1개 뿐이라면 시간을 리턴한다. 4. 만약 빙산이 연결되어있다면 ..

https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 크게 어려울만한 부분은 없는 BFS 문제이다. 좀 까다로운 부분이 있다면 3차원 배열을 써야 한다는 건데, 7569번 토마토를 풀었다면 풀 수 있다. (Tuple을 쓰면 좋다) 문자열 출력이라서 스펠링이나 띄어쓰기를 제대로 했는지 잘 봐야 하고(이것 때문에 3번 틀렸다;) 모든 입력이 0일 때 까지 테스트 케이스가 반복해서 주어진다는 것, 따라서 큐를 비워야 한다는 것 정도 알고 있으면 문제 푸는데 좀..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net M,N,K가 주어지고 K개의 직사각형이 주어질 때, 직사각형 부분을 제외한 나머지 영역들의 개수와 넓이를 구하는 문제이다. 왼쪽 아래부터 (0,0) 시작이라 좀 헷갈릴 수 있는데 개의치 않고 풀어도 상관없다. 어떻게 풀지 조금 생각하다가, 시작 점이 여러개인 BFS 풀듯이 직사각형이 아닌 모든 점을 시작점으로 생각하고, 방문한 정점은 바로 빼버리면 되겠다 싶어서 그렇게 풀기로 ..

https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 이 문제와 거의 유사한데, 5427번의 경우 불이 옮겨진 칸 또는 이제 불이 붙으려는..

문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 예제 입력 1 5 17 예제 출력 1 4 수빈이의 위치가 N이고 동생..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 ..