smsh0722.log
로그인
smsh0722.log
로그인
3109. 빵집
smsh0722
·
2022년 5월 3일
팔로우
0
DFS
Graph
Problem Solving
greedy
0
Greedy
목록 보기
2/5
문제
시간 제한:
1초
메모리 제한:
256MB
Problem Analysis
파이프를 최대한 벽에 밀착시켜 건설하면 된다. 따라서
Greedy
로 풀 수 있다.
Algorithm
DFS
를 하여 이동 가능한 인접한 칸으로 이동한다 (가장 위에 칸부터 조사하여, 가능한 경로를 탐색)
현재 칸을 벽으로 채운다 (파이프를 건설할 수 있는 경로이든 아니든 체크하기 위함)
오른쪽 끝에 도달하면 count += 1 해준다.
Data Structure
gasMap[]: 파이프관 지도를 저장
결과
Other
시간 복잡도는
O(RC)
이다.
smsh0722
Military service - May 31, 2022 ~ Nov. 30, 2023
팔로우
이전 포스트
1339. 단어 수학
다음 포스트
1700. 멀티탭 스케줄링
0개의 댓글
댓글 작성