티스토리 뷰
15684번: 사다리 조작
사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선
www.acmicpc.net
풀이
- 사다리를 코드로 어떻게 표현해야 할지 고민을 엄청 한 문제!!
- method를 기능별로 만들어서 풀었더니 군더더기 없이 한번에 통과!
- 이차원 배열을 만들고 한 column을 한 세로선이라고 두었다.
- 그리고 가로선은 인덱스 값을 줘서 표시했다.
- 이렇게 한 이유는 만약 1로만 표시하면 내려갈 때 양 옆에 가로선이 존재하면 이게 옆동네 가로선인지 내 가로선인지 알 길이 없다.
- 따라서 내 가로선인지 바로 구분하기 위해 인덱스를 두었다.
- 가로선은 3개가 넘어가면 -1을 출력하기 때문에 1~3개를 놓는 모든 방법에 대해 브루트포스를 돌렸다. - 조합과 백트래킹을 이용하면 된다.
- 사다리 세로선 하나를 잡고 내려가는 method를 반목문으로 세로선 개수만큼 돌려서 만약
i != i
가 하나라도 나오면 false로 체크하고 바로 다음 사다리 개수로 넘어가는 방식으로 했다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M, H, ans = -1; // H: row, N: column
static int[][] map;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
map = new int[H + 1][N + 1];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
map[x][y] = i + 1;
map[x][y + 1] = i + 1;
}
if (result()) ans = 0;
for (int i = 1; i <= 3; i++) {
if (ans > -1) break;
installLadder(0, i);
}
bw.write(String.valueOf(ans));
br.close();
bw.close();
}
public static void installLadder(int cnt, int L) {
if (cnt == L) {
if (result()) ans = L;
return;
}
for (int i = 1; i <= H; i++) {
for (int j = 1; j < N; j++) {
if (map[i][j] != 0 || map[i][j + 1] != 0) continue;
map[i][j] = (M + 1) + cnt;
map[i][j + 1] = (M + 1) + cnt;
installLadder(cnt + 1, L);
map[i][j] = 0;
map[i][j + 1] = 0;
}
}
}
// i -> i로 가는지 체크
public static boolean result() {
for (int j = 1; j <= N; j++)
if (!explore(j)) return false;
return true;
}
// 한 세로선에 대해 내려가는 동작 수행
public static boolean explore(int start) {
int x = 0;
int y = start;
while (x < H) {
if (map[x + 1][y] > 0) {
int ladderIdx = map[x + 1][y];
if (y > 1 && map[x + 1][y - 1] == ladderIdx) y--;
else if (y < N && map[x + 1][y + 1] == ladderIdx) y++;
}
x++;
}
if (y == start) return true;
return false;
}
}
'알고리즘' 카테고리의 다른 글
[백준] 1976. 여행가자 (Java) (0) | 2021.08.09 |
---|---|
[백준] 1939. 중량제한 (Java) (0) | 2021.07.29 |
[백준] 11559. Puyo Puyo (Java) (0) | 2021.07.23 |
[백준] 1504. 특정한 최단 경로 (Java) (0) | 2021.07.19 |
[백준] 16198. 에너지 모으기 (Java) (0) | 2021.07.16 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- java
- 해시
- 정규식
- 이분탐색
- CustomHook
- swea
- web
- form
- BigInteger
- 백준
- dfs
- 문자열
- 벨만포드
- 백트래킹
- 프로그래머스
- vue.js
- 우선순위큐
- 구현
- 시뮬레이션
- 브루트포스
- REACT
- 삼성역테기출
- Validation
- 그래프
- 알고리즘
- BFS
- matches
- regex
- dp
- 다익스트라
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함