자바(Java) 백준 3055 탈출 풀이
2022. 8. 9. 23:33
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 bfs로 문제를 풀었습니다. 고슴도치의 처음 위치를 찾고 큐에 넣어줍니다. 고슴도치가 움직일 때 마다 물이 차오르므로 이를 적용해야합니다. bfs에는 고슴도치가 움직인 횟수의 오름차순으로 들어가므로 isTurn 배열로 해당 횟수에 물이 차올랐는지 확인합니다. '고슴도치가 움직인 횟수 - 1' 배열에 값이 false 라면 인접한 빈칸에 물을 채워야합니다. 이중포문을 돌면서 각 칸마다 인접한 물이 있는..
자바(Java) 백준 16954 움직이는 미로 탈출 풀이
2022. 8. 9. 22:39
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 풀이 bfs로 문제를 풀었습니다. 먼저 움직인 횟수에 따른 체스판 모양을 구해야 합니다. 한 번 움직일 때 마다 체스판이 밑으로 움직이게 됩니다. 맨 밑에 있는 줄은 사라집니다. 맨 위에 있는 줄은 벽이 없는 상태로 생성됩니다. 체스판은 8 * 8 이므로 총 9가지의 체스판 모양이 생기며 8번 이상 움직인 경우에 체스판에 모든 벽이 사라지는 상태가 됩니다. 체스의 현재 위치와 움직..
자바(Java) 백준 2206 벽 부수고 이동하기
2022. 7. 27. 18:19
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 해당 문제는 bfs로 풀었습니다. 방문 체크를 벽을 부쉈을 때와 부수지 않았을 때 2가지 경우의 수에서 체크해주는 것이 까다롭습니다. 해당 위치, 벽을 부쉈는지 여부, 지나간 타일의 수를 저장할 Point클래스를 만듭니다. visited[][][]배열은 벽을 이미 부순경우, 부수지 않은 경우 2가지 경우의 수를 체크해줘야하기 때문에 3차원 배열을 사용합니다. 2..
자바(Java) 백준 14502 돌 그룹 풀이
2022. 7. 27. 16:00
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 풀이 dfs를 사용하여 풀었습니다. 먼저 세 숫자의 합이 3으로 나누어지지 않는다면 세 숫자의 합의 같을 수 없습니다. dfs로 (a, b), (b, c), (c, a) 세 가지를 선택한 경우로 진행합니다. 두 값에서 최대값과 최소값을 구하고 중복을 피하기 위해 visited[][] 배열에 방문 체크를 해줍니다. 탐색하면서 세 값이 같은 경우를 찾는다면 1을 출력해주면 됩니다. 코드 i..
자바(Java) 백준 14502 연구소 풀이
2022. 7. 27. 13:39
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 이 문제는 dfs와 bfs를 혼합하여 풀어주었습니다. 3개의 벽을 세울 때는 조합이므로 dfs를 사용하여 구하고, 바이러스를 인접 영역에 감염 시킬때는 dfs와 bfs 둘 다 사용가능할 것 같은데 저는 bfs로 풀었습니다. 3개의 벽을 세우는 createWall(int cnt, int idx) 메소드를 사용합니다. cnt는 벽을 세운 개수를 뜻하고 idx는 내가 이전에 벽을 세운 뒤 그 다음 위치를..
자바(Java) 백준 9019 DSLR 풀이
2022. 7. 26. 23:45
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 bfs로 문제를 풀어주면 됩니다. 숫자들을 계산할 때 이미 중간 계산결과로 나온 값은 방문체크를 해주고 큐에 넣지 않아야 시간초과를 면할 수 있습니다. 큐에 중간 계산 값과 현재까지 사용된 명령어들을 저장하기 위해 Info클래스를 생성해줍니다. 중간 계산 값이 이미 나온적이 있다면 넘어갑니다. 각 계산과정인 D, S, L, R값을 계산해주고 큐에 넣어주면 됩니다. 중간 값은..
자바(Java) 백준 16948 데스 나이트 풀이
2022. 7. 26. 21:45
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 풀이 해당 문제는 bfs로 풀었습니다. 체스말의 위치와 움직인 횟수를 저장하는 Night클래스를 만들어줍니다. bfs를 통해서 큐에 넣은 값을 꺼내서 체스말을 움직여줍니다. 6가지 방향은 dx, dy배열을 통해서 for문으로 6가지 방향을 선택하도록 구현하였습니다. visited배열에 움직인 위치를 방문했다는 것을..
자바(Java) 백준 16928 뱀과 사다리 게임 풀이
2022. 7. 26. 21:13
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/16928 [16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net](https://www.acmicpc.net/problem/16928) 풀이 bfs를 통하여 문제를 풀었습니다. 처음에 방문체크를 하지 않고 했더니 메모리 초과가 뜨네요. 한 번 방문한 지점은 다시 방문했을 때 큐에 들어가지 않도록 해주는 과정이 중요합니다. map에 사다리와 뱀 값을 넣어줍니다. 큐에 현재 위치와 움직인 횟수 정보를 담은 In..