본문 바로가기

CS/Algorism

 (99)
[백준] 5427. 불 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net bfs 문제로 크게 막힘없이 풀 수 있었다. 다만 주의할 점과 내가 놓친 부분은 다음과 같다. 상근이는 불이 붙으려는 칸으로 이동할 수 없다. 그리고 상근이가 있는 칸에 불이 옮겨옴과 동시에 상근이가 다른 칸으로 이동할 수 있다. 따라서 불이 먼저 이동하고, 상근이가 이동해야 한다. 불과 상근은 시간 당 한 칸씩 이동할 수 있다. 따라서 fireQue.size()만큼 각 불들이 한 칸씩 이동하도록 하고, pe..
[백준] 12100. 2048 (Easy) https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 상하좌우로 총 5번 움직였을 때 그래프에 있는 가장 큰 수를 구하는 문제이다. 따라서 상하좌우로 5번 움직이는 조합을 찾기 위해 재귀를 사용해야 한다. 그리고 상하좌우로 움직이는 로직을 구현해야 한다. 기존 배열을 보고 새로운 배열을 만들어야 한다. 새로운 배열에 값을 채울 인덱스인 fillIdx와 기존 배열과 값을 비교할 인덱스인 checkIdx가 필요하다. 기존 배..
[백준] 1697. 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 일차원 그래프의 bfs 문제이다. 주의할 점은 다음과 같다. 최소 시간을 구해야 하기 때문에 dfs가 아닌 bfs로 풀어야 한다. 최소 시간을 각 그래프의 위치에 저장해준다. 한 칸 뒤로 이동, 한 칸 앞으로 이동, 두배 앞으로 이동으로 한 위치당 총 3번의 탐색을 하면 된다. 그래프를 벗어나거나 이미 방문한 위치인 경우에는 탐색하지 않는다. (최소 시간을 갱신X) 내가..
[백준] 1541. 잃어버린 괄호 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 해결법을 떠올리는 건 쉽다. 연산의 최소 값을 구해야 하므로 -가 붙는 수를 최대한 크게 만들면 된다. 예를 들어 다음과 같이 식이 있다고 가정하자. a + b - c + d + e -f 그러면 -의 값을 최대한 크게 만들기 위해 c, d, e를 한 묶음으로 묶어주면 된다. 문제는 값이 입력될 때 숫자와 연산자를 어떻게 구분하고 어떻게 저장할지 고민이었는데.. -를 기준으로 먼저 나눈 ..
[백준] 4179. 불! https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net bfs 문제인데 이 문제를 풀며 주의할 점이 몇가지 있다. 논리적으로 불과 지훈이 동시에 이동해야 한다. 따라서 코드 상으로 불과 지훈이 순차적으로 한 번씩 이동해야 하는데, 둘 중에 불을 먼저 이동시켜야 한다. 불이 먼저 이동해서 불이 번지면, 지훈이가 불이 있는 곳을 피해서 이동해야 하기 때문이다. 불을 한 번 이동시킬 때는 fireQue의 사이즈만큼 이동을 처리해주어야 한다...
[백준] 7576. 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net https://olsohee.tistory.com/44 이 문제와 마찬가지로 bfs로 탐색하면서 이전 값에 + 1을 해주어 토마토가 익는데 걸리는 일수를 구하면 된다. 주의할 점은 우선 처음에 그래프 값을 입력받을 때 익은 토마토의 위치를 큐에 넣어주어야 한다. 그리고 큐에서 토마토의 위치를 빼서 해당 위치의 사방면을 탐색하고, 아직 익지 않은 토마토인 경우 이전 값 + 1을 저장..
[백준] 2178. 미로 탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 최소 거리를 구하는 문제이기 때문에 bfs를 사용하면 된다. 관건은 이동한 칸수를 계산하는 것인데, visited 배열에 1, 2, 3, ... 과 같이 이동한 칸수를 기록해주면 된다. 즉 visited 배열의 값이 0이면 아직 방문하지 않은 위치인 것이고, 시작 위치와 같이 한 번만에 방문하면 1, 그 다음으로 방문하면 2를 기록해주면 된다. 그리고 visited 배열의 값이 0이 아닌 경우, 즉 이미 방문한 경우에는 제외하기..
[백준] 1926. 그림 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net bfs 문제를 몇 달만에 풀어서 다 까먹었을까봐 걱정했는데 아주 쉬운 문제라서 그런지 잘 풀었다! 오랜만에 bfs를 푸는 만큼 쉬운 문제더라도 꼼꼼히 보자. bfs와 dfs 문제의 시간 복잡도는 O(V + E)이다. 이때 V는 노드의 개수, E는 간선의 개수이다. 주의해야 할 점은 다음과 같다. 방문 후에는 방문 처리를 해주어야 한다. 따라서 그림이면서 방문하지 않았을 경우에만 bfs를 시작하고, 이때..

티스토리툴바