Problem Solving/CT-Java

문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 시간초과가 나지 않을까? 처음에 효율적인 접근 방법이 있을까? 생각했다. 그런데 그냥 다음 로직처럼 구성하면 끝이였다. 상어 위치를 경로 큐에 넣는다. (스타트) 스타트에서 BFS 맵 전체를 탐색을 한다. BFS 탐색하면서 자신이 먹을 수 있는 물고기의 위치와 떨어진 거리를 다른 물고기 리스트에 저장한다 모든 맵의 거리와 물고기 위치를 탐색했으면 물고기 리스트를 순회한다 물고기 ..

문제 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 풀이 주사위의 전개도를 그려보고 이동했을 때 각 면이 어느 위치로 바뀌는지 생각하고 구현하면 되는 문제. 다음과 같이 접근하였다. 처음 주사위는 6면은 다음을 가리키고 있다. (참고로 문제 본문에서 제시하는 면의 숫자와 다르다. 본인 임의로 배치한 것) 상 : 1 , 하 : 4 좌 : 2 , 우 : 5 앞 : 3 , 뒤 : 6..

문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 괴랄한 정답률이 왜 나왔는지 알 수 있는 문제.. 처음에는 단순하게 한개의 벽을 부수고 BFS탐색하여 최단 경로를 구하려고 했는데 그렇게 쉽게를 문제가 나올리가 싶었다. 실마리를 찾지 못하다가. 질문글에서 다음 글을 보았다. 4번 항목을 보면 여기까지 오면서 벽을 부순 적이 있는가 여부를 큐에 저장해서.... 를 보고 벽을 깬 여부를 맵을 탐색하면서 같이 체크하..

문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 문제에서 주어진 조건을 확인하자. R X C 행열로 주어지고 비어있는 곳은 ' . ' , 물이 차 있는 지역은 ' * ' , 돌은 ' X ' 로 표시되어 있다. 비버의 굴은 'D' 고슴도치 위치는 'S' 로 나타내어져 있다. 문제에서 원하는 것은 고슴도치 'S'가 비버의 굴 'D'까지 이동할 수 있다면 걸린 최소 시간을 구하는 것이 목적이다. 문제에서는 고슴도치는 물에 바쪄 죽지 않기 위해 물이 차..

문제 문제링크 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 일일히 한 원소씩 토글하여 풀었음 하지만 이렇게 풀면 배열의 길이가 길어질 수록 매우 비효율적인 풀이방법임. 위의 방법과 다르게 왼쪽부터 배열원소를 탐색하면서 처음에는 0을 탐색하고 0값과 다른값이 나오면 카운트를 증가하고 1을 다시 탐색하여 토글하는 방법으로 검사하는 것이 더 빠름. 비 효율적인 풀이 (하나씩 원소를 변경) import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.stream.Stream; public class SWEA_1289 { pu..

문제 https://www.acmicpc.net/problem/1244 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 풀이 스위치 토글 배열은 선언하면 쉽게 구현할 수 있는 문제 여학생 입력에서 왼쪽 오른쪽 인덱스를 지정해서 범위안에 전부 토글하면 해결할 수 있다. package BOJ.Implementation; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.u..

문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS를 사용하여 최단 거리를 구하는 문제다. 이전에 BFS를 이용하여 풀어보아서 DFS로 시도하였다. 그러나 DFS로 가지치기를 잘 하지 않는이상 input데이터 범위가 10만이여서 시간초과가 날수밖에없다. DFS로 계속시도하였는데 가지치기를 잘한 DFS풀이를 보고 그냥 최단거리는 BFS를 사용하는것이 정신건강에 이롭다는 것을 느꼈다. BFS풀이를 할 때에도..

문제 https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 풀이 조합으로 궁수의 위치를 뽑고 시뮬레이션을 하였다. 다른 풀이를 보면 BFS를 사용해 궁수부터 적 위치까지 탐색을 한 풀이들이 많은데 본인은 그렇게 하지않고 왼쪽 하단 부터 오른쪽 상단까지 열 순서가 아닌 행 순서로 탐색하였다.(좌 하->상 ... 우 하->상) 그리고 탐색하면서 시간마다 적이 성벽에 닿으면 사라진다. 배열을 N+1, M 크기만큼 구현하여 N+1 위치에 성벽 위치를 지정하였다. 그리..

문제 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 0,0 좌표부터 시작하여 중복되지 않은 알파벳을 탐색하여 가장 긴 길이를 구하는 문제이다. 처음에는 단순하게 DFS 탐색을 하며 탐색했던 알파벳을 List에 넣어서 새로운 좌표를 탐색할 때마다 List에 알파벳이 중복되는지 검사하였다. 그런데 이렇게 하면 시간초과가 발생하여 통과하지 못한다. 그렇다면 어떻게 접근하면 좋을까? 내 생각은 List에 넣고서 contain 사용해 있는..

문제 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 풀이 좌측 열에서부터 우측 열까지 놓을 수 있는 파이프의 최대 갯수를 구하여야 한다. DFS를 사용하여 한칸씩 우측열로 이동할 때마다 우측 상단, 우측, 우측 하단 순으로 파이프를 놓을 수 있는지 없는지 탐색하였다. 좌측 열 처음부터 우측 열 끝까지 도달하면 파이프를 놓을 수 있는 갯수를 추가하였는데 이 때 파이프가 우측 열 끝가지 도달하던(경로탐색 성공), 도달하지 않던(경로탐색 실패) 이전에 탐색한 경로..