백준 1012
-
[백준 1012] - [dfs] - 유기농 배추 (JAVA)알고리즘/BFS_DFS 2018. 12. 19. 17:00
문제 링크 : https://www.acmicpc.net/problem/1012 이 문제는 DFS 간단하게 풀 수 있는 문제이다. 다만 주의해야 할 부분이 있는데 제한시간은 1초인데 여러개의 테스트 케이스가 주어지니 제한시간내에 모든 테스트 게이스를 풀기 위해선 불필요한 좌표까지 dfs로 접근할 필요가 없다. 배추의 좌표를 정수형 배열 타입의 큐에 저장한다. 모든 입력이 완료되고 queue가 빌때까지 queue에서 하나씩 추출해가면서 dfs를 돌린다. queue에 있는 좌표는 부조건 배추가 심어저 있는 좌표이다. 추출된 좌표가 이전에 방문한 이력이 없는 경우만 dfs 탐색을 한다. 위에 나열한 순서와 조건으로 DFS 탐색을 시도하면 문제는 아주 쉽게 풀린다. 모든 좌표에 방문여부와 배추가 심어진 좌표인지..