자바(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) 백준 14442 벽 부수고 이동하기 2 풀이
2022. 8. 5. 21:54
알고리즘 풀이/백준
문제 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 풀이 bfs를 활용하여 문제를 풀었습니다. 이 문제의 핵심은 벽을 부순 횟수에 따라 방문체크를 따로 해주어야 반례를 피할 수 있습니다. 벽 부수고 이동하기 문제를 참고해주세요. 자바(Java) 백준 2206 벽 부수고 이동하기 풀이 위 문제에서 벽을 부술 수 있는 횟수만 k번으로 변형된 문제입니다. 풀이방식은 비슷합니다. 코드 package code; im..
자바(Java) 백준 16946 벽 부수고 이동하기 4 풀이
2022. 8. 5. 17:26
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 시간 초과 때문에 여러 번 실패한 문제입니다. 일반적인 BFS 로는 시간초과가 나는 문제입니다. 이 문제에서 중요한 포인트는 인접한 빈칸들 끼리 그룹화를 해줘야 합니다. 그룹화하는 방법 위 그림과 같이 벽으로 나눠진 빈칸들을 그룹별로 나누어서 개수를 카운트 해줍니다. 그 이후에 각각의 벽에서 4방향으로 인접한 그룹들을 카운트해주면 됩니다. 코드 import java..
It 개발자 면접 참고 사이트
2022. 7. 28. 11:28
면접
신입 개발자로 들어가기 위해 면접 준비가 필요한데요. 이 때 참고할 만한 사이트를 추천드릴게요. 1. 한재엽님 깃허브 https://github.com/JaeYeopHan/Interview_Question_for_Beginner GitHub - JaeYeopHan/Interview_Question_for_Beginner: Technical-Interview guidelines written for those who started studying progr :boy: :girl: Technical-Interview guidelines written for those who started studying programming. I wish you all the best. :space_invader: - Gi..
자바(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는 내가 이전에 벽을 세운 뒤 그 다음 위치를..