BFS

https://www.acmicpc.net/problem/7576 문제분석이 문제는 2차원 격자에서 익은 토마토가 하루마다 상하좌우로 인접한 안 익은 토마토를 익게 만드는 구조라서, 여러 시작점이 동시에 퍼지는 BFS 문제라고 보고 접근하였다.입력 받을 때 처음부터 익어 있는 토마토 좌표들을 전부 모아서 한 번에 시작하도록 리스트에 담고 큐에 넣었고, 빈 칸(-1)은 애초에 방문 처리해서 전파 대상에서 제외한다. 전체 칸 수에서 빈 칸 수랑 처음 익은 토마토 수를 더해서 이미 다 익어 있는 경우는 바로 0 출력하게 처리했다. 그 다음에는 큐에 “같은 날에 익는 토마토 묶음” 단위로 넣어서 레벨 단위 BFS처럼 돌렸고, 각 좌표에서 상하좌우로 아직 방문 안 한 칸만 다음 날 리스트에 추가하면서 방문 처리하..

https://www.acmicpc.net/problem/2667 문제분석DFS/BFS 연습용 문제를 풀기 위해 이 문제를 정했다. 문제를 보면 단지를 구하는 것이다. 단지를 그래프라고 생각하고, 그래프를 전부 순회하도록 코드를 작성하면 된다. 따라서 DFS/BFS 둘 중 아무거나 선택해도 문제를 풀 수 있게 되어있다. DFS/BFS를 공부하며 배운 구조를 활용하여 문제를 해결하면 될 것이라 생각했다.구현에서, queue에 뭘 저장해야 하나 고민했었는데, 문제에서 주어진 N의 최대값이 25인 점을 활용하여, row*25+col값을 저장하고, poll한 뒤 25로 나눈 몫과 나머지를 적용할 수 있게끔 하였다. 코드BFSDFS 바꾸기 용이하다.BFS용 메서드 offer과 poll 대신DFS용 메서드 push..

DFS : Depth-First Search - 깊이 우선 탐색가능한 한 깊이 들어가며 탐색한 뒤, 더 이상 갈 수 없을 때 되돌아오는 방식. 스택 구조를 기반으로 하며, 재귀 또는 명시적 스택 이용한다. JAVA는 구조적으로 JVM에서 각 쓰레드별로 고정된 크기의 콜 스택을 주며, 이 크기가 매우 작다. 따라서 많은 재귀 depth를 가지지 못한다. 그러므로 명시적으로 스택 자료구조를 사용한다.DFS 구현 시 유의사항1. 재귀 깊이를 구현 언어가 감당할 수 있는지 확인(JAVA는 위험이 큼).2. 방문 체크(visited) 필요 - 무한 탐색을 막기 위함(트리가 아닌, 사이클의 경우). BFS : Breadth-First Search - 너비 우선 탐색시작 정점에서 가까운 정점부터 차례로 탐색, ..