pair
-
[DFS/BFS] 문제이름 : 음료수 얼려 먹기Algorithm/유형별 문제 풀기 2021. 7. 5. 11:59
문제 설명 N X M 크기의 얼음 틀이 있다. 구멍이 뚫린 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상 하 좌 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 1. 사용 알고리즘 그래프 탐색 - BFS & DFS 2. 문제 해결 아이디어 주어진 좌표의 위치와 해당 위치의 상하좌우에 대해 구멍이 뚫려서 연결되어 있는지 탐색하면 된다. 이때 주어진 2차원 배열을 그래프 형태로 생각하면, DFS와 BFS 알고리즘을 적용해 해결할 수 있다. 3. 코드 구현방식1) BFS(너비 우선 탐색)를 사용해 가까운 좌표부터 확인하기 각 좌표가 상하좌우에 대해 움직일 수 있는 ..