알고리즘/백준
BOJ) 파이프 옮기기 1
Zin0_0
2020. 7. 8. 19:37
반응형
파이프 옮기기 1
17070번: 파이프 옮기기 1
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의
www.acmicpc.net
풀이
옮길 수 있는 모든 경우의 수를 찾는 문제기 때문에 브루트포스 문제다.
직접 다 돌리는데는 BFS나 DFS만큼 편한게 없다고(?) 생각해서 DFS로 풀었다.
문제를 풀면서 막혔던 부분은
첫째로, 문제 조건을 잘못 이해했다는 것이다.
파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수
이 문구에서 N,N을 보지 않고 N,y or x,N으로 이동한 파이프들을 구해줬었다...
두번째로는 실수라기 보다는 기둥의 시작점인 (0,0)에서 시작했다는 것이다.
편의상 기둥의 상단과 하단이 있다고 친다면, 처음 기둥의 상단이 0,0 에 하단이 1,0에 존재한다.
여기서 상단을 기준으로 로직을 짰는데, 뭔가가 어긋났는지 잘 안됐다.
그래서 하단인 (1,0)부터 시작을 해주고 조건을 바꿔주었다.
위의 두 부분을 신경쓰니까 바로 통과됐다.
dfs를 통해서 기둥이 N,N에 도달하는 지점 (코드에서 n-1,n-1에 도달하는 지점)을 찾아서 답을 구해주었고,
가로,세로,대각선인 경우에 움직일 수 있는 방향을 switch문을 통해 지정해줬다.
N이 3~16이나 돼서 효율이 좋지 못했다.
하지만, 다른 방법은 딱히 떠오르지 않아서 다르게 풀어보는 것은 포기했다.
대신 코드를 조금 더 줄이기 위해 if 문이 여러개 쓰이는 부분을 조금 수정해주었다.
방향에 따라 움직이는 방법을 정해주는 부분은 for문을 통해서 바꿔줬고
움직일 수 있는지 확인하는 canMove 부분의 if문을 줄이기 위해서, 가로 세로로 움직이는 horizon과 vertical 변수를 dx dy로 각 방향마다 다음 좌표로 움직일 수 있도록 설정해줬다.
효율을 크게 좋지는 않지만, 코드 라인이 줄어든 것에 만족한다.
코드 1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
final static int[] horizon = {1,0}, vertical = {0,1};
final static int BLANK =0, WALL =1;
static int answer, n, map[][];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
map = new int[n][n];
for(int i=0; i<n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0; j<n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
solution();
br.close();
}
private static void solution() {
answer =0;
dfs(new PipePos(1,0,0)); // 끝 부분으로 시작하기
System.out.println(answer);
}
private static void dfs(PipePos pipePos) {
if(pipePos.x ==n-1 && pipePos.y == n-1) {
answer++;
return;
}
int dir = pipePos.direction;
int x = pipePos.x;
int y = pipePos.y;
switch (dir) {
case 0: // 가로, 대각선 가능
if(canMove(x,y,0)) {
dfs(new PipePos(x+horizon[0],y,0));
}
if(canMove(x,y,2)) {
dfs(new PipePos(x+horizon[0],y+vertical[1],2));
}
break;
case 1: // 세로, 대각선 가능
if(canMove(x,y,1)) { dfs(new PipePos(x,y+vertical[1],1)); }
if(canMove(x,y,2)) { dfs(new PipePos(x+horizon[0],y+vertical[1],2)); }
break;
case 2: // 가로, 세로, 대각선 가능
if(canMove(x,y,0)) { dfs(new PipePos(x+horizon[0], y, 0)); }
if(canMove(x,y,1)) { dfs(new PipePos(x,y+vertical[1],1)); }
if(canMove(x,y,2)) { dfs(new PipePos(x+horizon[0], y+vertical[1], 2)); }
break;
default:
break;
}
}
private static boolean canMove(int x, int y, int dir) {
int nextX = x+horizon[0];
int nextY = y+vertical[1];
if(dir ==0) { // 가로
if(nextX >=n) { return false; }
if(map[y][nextX] == WALL) { return false; }
} else if(dir ==1) { // 세로
if(nextY >=n) { return false; }
if(map[nextY][x] == WALL) { return false; }
} else { // 대각선
if (nextX >= n || nextY >= n) { return false; }
if (map[nextY][nextX] == WALL || map[y][nextX] == WALL || map[nextY][x] == WALL) { return false; }
}
return true;
}
}
class PipePos {
int x;
int y;
int direction; // 0 : 가로, 1 : 세로, 2 : 대각선
public PipePos(int x, int y, int direction) {
this.x =x;
this.y =y;
this.direction = direction;
}
}
코드 2
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
final static int[] dx = {1,0,1}, dy = {0,1,1};
final static int WALL =1;
static int answer, n, map[][];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
map = new int[n][n];
for(int i=0; i<n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0; j<n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
solution();
br.close();
}
private static void solution() {
answer =0;
dfs(new PipePos(1,0,0)); // 끝 부분으로 시작하기
System.out.println(answer);
}
private static void dfs(PipePos pipePos) {
if(pipePos.x ==n-1 && pipePos.y == n-1) {
answer++;
return;
}
int dir = pipePos.direction;
int x = pipePos.x;
int y = pipePos.y;
switch (dir) {
case 0: // 가로, 대각선 가능
for(int i=0; i<3; i++) {
if(i != 1) {
if(canMove(x,y,i)) { dfs(new PipePos(x+dx[i], y+dy[i], i));}
}
}
break;
case 1: // 세로, 대각선 가능
for(int i=1; i<3; i++) {
if(canMove(x,y,i)) { dfs(new PipePos(x+dx[i], y+dy[i], i)); }
}
break;
case 2: // 가로, 세로, 대각선 가능
for(int i=0; i<3; i++) {
if(canMove(x,y,i)) { dfs(new PipePos(x+dx[i], y+dy[i], i));}
}
break;
default:
break;
}
}
private static boolean canMove(int x, int y, int dir) {
int nx = x+dx[dir], ny = y+dy[dir];
if(nx >=n || ny >=n) { return false; }
if(map[ny][nx] == WALL) { return false; }
if(dir ==2) {
if(map[ny][x] == WALL || map[y][nx] == WALL) { return false; }
}
return true;
}
}
class PipePos {
int x;
int y;
int direction; // 0 : 가로, 1 : 세로, 2 : 대각선
public PipePos(int x, int y, int direction) {
this.x =x;
this.y =y;
this.direction = direction;
}
}반응형