dfs3 [Java] 백준 1194번 달이 차오른다, 가자. 문제 952hi의 접근방법 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 1. 접근방법 길 찾기 문제는 bfs라는 공식을 매번 기억하고 있었는데 왠지 dfs로 재귀를 타고 싶었다. dfs나 bfs 문제 둘다 중복방문 처리가 핵심이라고 생각했다. 처음 문제를 읽고 알파벳 a~z 모두 등장한다고 생각해서 알파뱃 개수인 26개 배열과 키의 개수를 가지고 재귀를 돌리면서 매번 4방탐색을 해준다면 가뿐하다고 생각했다. 그런데 시간초과를 발생했다. .. 2022. 5. 12. [Java] 백준 1520 내리막 길 952hi의 접근방법 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. 접근방법 보자마자 그저그런 최단거리 BFS 문제라고 판단하고 바로 큐에 넣어서 최단거리를 구해줬다. 예제 입출력 또한 잘나오지만 시간초과가 맞왜틀 발생한다. 단순하게 50*50*4 = 100,000 이라고 생각했지만 약 4의50약 2^100 => 엄청나게 큰수가 나와서 터지는 게 당연했다. 이 문제는 스스로 풀었다기 보다는 여러 정보를 조합해 스스로 풀어봤다. 메모이제이션과 DFS를 활용해 문제를.. 2022. 4. 21. [Java] 백준 19236 청소년 상어 https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 1. 접근방법 1. 문제를 읽어보면 딱히 어려운 설명은 없어서 천천히 읽어보고 이해한 후 풀어야 겠다고 생각함 2. 물고기 이동 함수, 상어 재귀 함수, 딥카피 함수 3개가 있으면 편하겠다고 생각함 2. 어려웠던점 좌측과 우측은 서로 독립적인 공간에서 작업하고 돌아오기에 같은 값으로 돌아와야했다. 하지만 그렇지 않았다... 객체를 생성하고 딥카피 할때 일반적인 2차원 배열처럼 복.. 2022. 4. 7. 이전 1 다음
