BFS3 [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] 백준 11559 뿌요뿌요 Puyo Puyo https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 1. 접근방법 1. bfs를 통해서 블럭이 4개가 인접해있는지 판단하고 맞으면 부쉬고 내려줘야겠다 2. 내리는 함수 down, 확인함수 및 파괴 check를 구현하면 되겠다. 2. 어려웠던 부분(실수) 1. 색을 총 5개 입력받아야 하는데 4개만 받아서 로직은 맞지만 틀려서 뭐때문인지 찾는게 힘들었다. 맞왜틀 2. 연쇄 폭발 횟수와 총 폭발 횟수를 혼돈했다. ex)입력받은.. 2022. 4. 6. [JAVA] 2206 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 접근방법 1. 기본적으로 최단거리 찾기 문제라 바로 BFS가 떠올랐다. 2. BFS 돌릴때 모든 맵의 벽을 모두 한번씩 지워보며 가면 정답이 나오겠네 시간초과 (맞왜틀?) 3. 그럼 가는길에 부술수있으면 부수고 아니면 그냥 갈길 가면서 BFS 타보자 시간초과,메모리 (맞왜틀?) 4. 갈때 부순경우 안부순경우 모두 체크해서 큐에 넣자 (이게맞네?) 느낀점 고정관념을 버려야 .. 2022. 3. 24. 이전 1 다음
