혼자 공부하는 공간

안녕하세요 GODZ입니다. 오늘은 BFS를 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 2020/06/24 - [알고리즘/BFS] - [JAVA] 백준 2667. 단지번호붙이기 (BFS) :: 로직/코드 - GODZ [JAVA] 백준 2667. 단지번호붙이기 (BFS) :: 로직/코드 - GODZ 안녕하세요 GODZ입니다. 오늘은 BFS을 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 단지의 탐색의 종료와 새 단지의 탐색의 시작 사이에 단지 수를 +1 합니다. 각 단지의 집 수� godzz.tistory.com 위의 문제 기억하시나요? 인접한 칸들을 한 단지로 보고 단지의 갯수를 카운트하는 문제였습니다. 이 문제도 무방향 그래프에서 연결된 정점들을 ..

안녕하세요 GODZ입니다. 오늘은 BFS를 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 각 위치를 하나의 노드라고 생각하고, 이동할 수 있는 위치(+1, -1, *2)에 대해 각각을 다음에 탐색할 노드라고 생각하면 BFS로 풀 수 있습니다. 이전 BFS 문제들과는 달리 각 노드에 대한 연결관계를 설정하지 않아도 되기에 더 간단하게 풀 수 있습니다. 4. 로직 플로우 차트를 통해 보여드리겠습니다. 다음엔 더 깔끔한 플로우 차트를 만들겠습니다. 만들고 나니 깔끔하지는 않네요. 여기서 방문체크 및 이동 횟수를 저장할 자료구조를 배열과 해시맵을 통해 각각 구현을 해보았습니다. 다음 위치 N'를 Key로, 이동 횟수를 Value를 가지는 HashMap 다음 위치 N'를 Index로, ..

안녕하세요 GODZ입니다. 오늘은 BFS을 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 단지의 탐색의 종료와 새 단지의 탐색의 시작 사이에 단지 수를 +1 합니다. 각 단지의 집 수를 오름차순으로 정렬해야하기 때문에 해당 정보를 위한 자료구조를 만듭니다. 2에서 나눈 단지 번호와 집의 수가 맵핑되지 않아도 되기 때문에 Map구조가 아닌 List나 배열을 사용하셔도 좋습니다. (저는 처음에 문제를 제대로 안읽어서 HashMap을 사용했습니다.) 4. 로직 2차원 배열을 순회하며 값이 1이고, 해당 좌표가 방문한 적이 없는 곳인 경우 단지 카운트를 증가, 방문 값을 true로 바꾸고 현재 좌표를 큐에 넣습니다. 큐 poll()로 값을 추출하고, 해당 단지의 집 갯수를 위해 집 카..

안녕하세요 GODZ입니다. 오늘은 BFS를 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 지도 정보를 담을 2차원 배열 생성합니다. 시작이 (0,0) 이 아닌 (1,1) 이기 때문에 개인적으로 인덱스에 대한 혼동이 오지 않도록 (N+1) x (M+1) 크기로 만들었습니다. 좌표를 큐에 저장할 때는 클래스로 만드는 게 편리합니다. 상/하/좌/우 인접한 좌표로 이동할 수 있기 때문에 해당 좌표가 방문했던 곳인지 아닌지를 판단하기 위해 같은 크기의 2차원 배열이 필요합니다. 상/하/좌/우에 대해 검사할 때는 dx(상하좌우 각각에 대한 x좌표 변경값), dy(상하좌우 각각에 대한 y좌표 변경값)의 배열을 만들어 반복문을 통해 체크합니다. 5번의 경우 dx, dy 배열을 만드는 이유는 ..