문제 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 풀이 재귀로 구현한 DFS와 큐로 구현한 BFS로 해결할 수 있다. 영역과 영역의 크기는 mutableList를 이용해 저장해주었다. graph는 false로 초기화 되어있는 BooleanArray를 이용했다. 입력받은 직사각형이 지나는 좌표는 true로 바꾸어준다. 이때 주어진 좌표의 기준점이 왼쪽 위(graph[0][0])가 아니라 아래(graph[rows][0])인 것을 주의해서 for문을 만들어 주어야한다. graph를 순회하며 ..

문제 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 재귀로 구현한 DFS와 큐로 구현한 BFS로 해결할 수 있다. 단지와 집의 수는 mutableList를 이용해 저장해주었다. 주어진 graph를 순회하며 방문한적이 없고 graph가 1인 경우 단지를 추가하고 DFS나 BFS를 호출한다. DFS의 경우에는 graph가 방문하지않고 1인 경우에 다시 DFS함수를 호출해주고, 호출될 때 마다 집의 수를 1 증가시킨다. BFS의 경우에는 해당하는 경우에 Queue에 추가해주고 집의 수를 1 증가시킨다. 리스트..

문제 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 입력받은 그래프를 너비 우선 탐색(BFS)을 이용해 풀이하면 된다. BFS로 풀이할 때, 일반적으로는 graph와 같은 크기로 Boolean 배열인 visited를 만들고 방문 체크를 해준다. 그렇지만 이번 문제에서는 visited를 사용하지 않았고, graph[x][y]가 1일 때만 graph[x][y]를 갱신해주는 방법을 이용하였다. graph[x][y]가 0인 경우(벽)와 1 이상인 경우(이미 방문함)에는 방문하지 않기 때문에 최단거리를 알 수 있다. 코드 import java..