문제 : https://www.acmicpc.net/problem/15684
15684번: 사다리 조작
사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로
www.acmicpc.net
문제 요약 : i번째로 출발해 i가 나오도록 선을 긋는 최소 횟수
| 입력 | 출력 |
|
2 ≤ N(열) ≤ 10 1 ≤ H(행) ≤ 30 0 ≤ M(사다리) ≤ (N-1)*H M개의 사다리값 |
i번째로 출발해 i가 나오게 만드는 최소 조작 횟수
|
JAVA - 수정 후
| 채점 번호 | 아이디 | 문제 번호 | 결과 | 메모리 | 시간 | 언어 | 코드 길이 |
| 16394816 | cbkpar | 15684 | 맞았습니다!! | 15592KB | 1796ms | Java | 1628B |
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
static int n,m,h;
static int[][] ladder;
static int ans = 4;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int i;
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
ladder = new int[h][n];
for(i=0;i<m;i++) {
st = new StringTokenizer(br.readLine());
ladder[Integer.parseInt(st.nextToken())-1][Integer.parseInt(st.nextToken())-1]=1;
}
if(m==0) {
ans=0;
}else {
dfs(0,0);
}
ans=ans==4?-1:ans;
bw.write(ans+"\n");
br.close();
bw.close();
}
static void dfs(int w, int k) {
if(k>=ans) return; // 현재까지 구한 최솟값보다 같거나 크면 리턴
int i;
for(i=0;i<n-1;i++) { //n-1개가 똑같다면 나머지 하나는 당연히 같으므로 n까지 조사하지 않음
int tmp = i;
for(int j=0;j<h;j++) {
if(ladder[j][tmp]==1) {//현재위치에 사다리가 있다면 오른쪽으로 한칸
tmp++;
continue;
}
if(tmp==0) continue;
if(ladder[j][tmp-1]==1) {//현재위치-1에 사다리가 있으면 왼쪽으로 한칸
tmp--;
continue;
}
}
if(tmp!=i) break;//시작한 사다리가 끝난 사다리와 다르면 종료
}
if(i==n-1&&k<ans) {//맞은 개수가 n-1개라면
ans = k;
return;
}
for(i=w;i<n*h;i++) {
int dy = i/n;//초기값을 행렬안에 적지 않고 밖에 공통으로 적어줌
int dx = i%n;
if(i%n>0) {
if(ladder[dy][dx-1]==1) continue; //왼쪽에 사다리가 있을경우 다음으로
}
if(i%n>=n-1) continue; //마지막에는 더이상 마지막으로 갈 수 없으므로 다음으로
if(ladder[dy][dx+1]==1) continue; //오른쪽에 사다리가 있을 경우 다음으로
if(ladder[dy][dx]==0) {
ladder[dy][dx]=1;
dfs(i+2,k+1);
//사다리를 추가했을경우 연속할 수 없으므로 i+1이아닌 i+2로 한다.
ladder[dy][dx]=0;
}
}
}
}느낀점 1: dy dx의 경우 i/n, i%n으로 행렬식 안에 넣었지만 이렇게 할경우 연산이 많아진다는 점 확인
느낀점 2: 연속할 경우에는 i+1번째가 아닌 그다음을 검사해도 된다.
느낀점 3: 1개만 틀릴 수 있는 경우는 존재 하지 않으므로 1번부터 n번까지 조사하지 않아도 된다.
느낀점 4:세로로 푸는것이아닌 가로로도 푸는 방법이 존재한다 행마다 열이 있는경우 결과를 바꿔주면된다.
//하지만 중간에 결과를 알 수 없고 끝까지 검사를 해야 한다는 단점이 있음
느낀점 5: 리스트로 미리 빈칸을 받거나 조건문을 개선하면 시간을 많이 단축 할 수 있을 것 같다.
JAVA
| 채점 번호 | 아이디 | 문제 번호 | 결과 | 메모리 | 시간 | 언어 | 코드 길이 |
| 16385137 | cbkpar | 15684 | 맞았습니다!! | 15812KB | 2036ms | Java | 1549B |
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
static int n,m,h;
static int[][] ladder;
static int ans = 4;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int i;
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
ladder = new int[h][n];
for(i=0;i<m;i++) {
st = new StringTokenizer(br.readLine());
ladder[Integer.parseInt(st.nextToken())-1][Integer.parseInt(st.nextToken())-1]=1;
}
dfs(0,0);
ans=ans==4?-1:ans;
bw.write(ans+"\n");
br.close();
bw.close();
}
static void dfs(int w, int k) {
if(k>=ans) return;
int i;
for(i=0;i<n;i++) {
int tmp = i;
for(int j=0;j<h;j++) {
if(ladder[j][tmp]==1) {
tmp++;
continue;
}
if(tmp==0) continue;
if(ladder[j][tmp-1]==1) {
tmp--;
continue;
}
}
if(tmp!=i) break;
}
if(i==n) ans=Math.min(ans, k);
for(i=w;i<n*h;i++) {
if(i%n>0) {
if(ladder[i/n][i%n-1]==1) continue;
}
if(i%n>=n-1) continue;
if(ladder[i/n][i%n+1]==1) continue;
if(ladder[i/n][i%n]==0) {
ladder[i/n][i%n]=1;
dfs(i+1,k+1);
ladder[i/n][i%n]=0;
}
}
}
}'백준온라인' 카테고리의 다른 글
| [백준온라인] 11659번 구간 합 구하기4 (0) | 2019.12.10 |
|---|---|
| [백준온라인] 15685번 드래곤 커브 (0) | 2019.12.10 |
| [백준온라인] 15683번 감시 (0) | 2019.12.06 |
| [백준온라인] 14891번 톱니바퀴 (0) | 2019.12.06 |
| [백준온라인] 14890번 경사로 (0) | 2019.12.05 |
