티스토리 뷰
반응형
#. Problem
* The copyright in this matter is in BOJ
#. Resolution Process
1. Read and understand problem
2. Redefine the problem + abstract
3. Create solution plan (select Algorithm, Data structure)
4. Prove the plan (check performance time and usage memory)
5. Carry out the plan
6. Look back on the plan and find a way to improve it
#. Solve
전체적인 흐름은
차근차근 파이프를 설치해보면서 원웅이네 빵집까지 파이프가 연결된다면
count 해주면 되는데..!
여기에 그리디 알고리즘을 적용한다면 더 쉽게 접근할 수 있다.
"오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선"으로 연결할 수 있다고 했는데,
"오른쪽 위 대각선 -> 오른쪽 -> 오른쪽 아래 대각선"순서로 연결을 시도해본다면,
한 번에(?) 최적의 해를 구할 수 있다.
왜냐하면, 연결할 수 있는 가장~ 위로 붙여서 파이프를 설치하다보면
아래에서 파이프를 연결할 수 있는 공간이 더 많이 생기기 때문이다.
결국 이는 놓을 수 있는 파이프라인의 최대 개수가 된다.
#. Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ3109_v2 { static int R, C, res; static char map[][]; static boolean visited[][]; static int[] dr = { -1, 0, 1 }; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); R = Integer.parseInt(st.nextToken()); C = Integer.parseInt(st.nextToken()); map = new char[R][]; visited = new boolean[R][C]; for (int i = 0; i < R; i++) map[i] = br.readLine().toCharArray(); // 근처 빵집으로부터 가스관 연결을 시도해보자.(0행 ~ R-1행) for (int i = 0; i < R; i++) { visited[i][0] = true; setPipe(i, 0); } System.out.println(res); } // 가스관 연결 // 오른쪽 위 대각선, 오른쪽, 오른쪽 아래 대각선 순서로 연결 시도 private static boolean setPipe(int r, int c) { // 원웅이네 빵집까지 파이프가 연결되었다면 if(c == C-1) { res++; return true; } int rr, cc = c + 1; for (int d = 0; d < 3; d++) { rr = r + dr[d]; // row 범위가 넘어가면 pass if(rr < 0 || rr >= R) continue; // 건물이 있거나 이미 파이프가 설치되(려던 시도가 있)었다면 pass if(map[rr][cc] == 'x' || visited[rr][cc]) continue; // 해당 공간에 파이프를 설치할 수 있다면 설치해보자. visited[rr][cc] = true; // 해당 방향으로 파이프가 제대로 설치되었다면 더이상 다른 방향을 확인하 필요가 없음 if(setPipe(rr, cc)) return true; } // 파이프를 제대로 설치하지 못했을 경우 return false; } } | cs |
반응형
'PS > Problem_Solving' 카테고리의 다른 글
[BOJ] 14889. 스타트와 링크(백트래킹).java (0) | 2020.08.28 |
---|---|
[BOJ] 1987.알파벳(DFS,백트래킹).java (2) | 2020.08.27 |
[BOJ] 1194.달이 차오른다, 가자(BFS, BitMask).java (0) | 2020.08.26 |
[BOJ] 14442.벽 부수고 이동하기 2(BFS).java (0) | 2020.08.26 |
[BOJ] 2206.벽 부수고 이동하기(BFS).java (0) | 2020.08.26 |
댓글