파이프 옮기기(백준 17070번, 자바)

 

https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

 

1. 큐 사용

 

2. 이전 이동 방향이 대각선인 경우 다음으로 이동이 가능한 좌표: (x+1, y), (x,y++1), (x+1,y+1) 

위의 세 가지의 pipe 값이 어느것 하나라도 1이라면 이동 불가능하다!!

 

 

import java.util.*;


class Solution
{
	static int pipe[][];
	static Queue<Point> q;
	static int N;
	static int answer=0;
	
	public static void main(String args[]) throws Exception
	{
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		pipe=new int[N][N];
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				pipe[i][j]=sc.nextInt();
			}
		}
		
		
		q=new LinkedList<Point>();
		q.add(new Point(0,1,1));
		
		while(!q.isEmpty()) {
			
			if(pipe[N-1][N-1]==1) break;
			Point p=q.poll();
			
			if(p.x ==N-1 && p.y ==N-1) answer++;
			else if(pipe[p.x][p.y]!=1)
				check(p.x,p.y,p.direction);

		}
		System.out.println(answer);
		
		
	}
	
	static void check(int x, int y, int direction) {
		
		switch(direction) {
		case 1: 
			move_1(x,y);
			move_2(x,y);
			break;
		case 2:
			move_1(x,y);
			move_2(x,y);
			move_3(x,y);
			break;
			
			
		case 3: 
			move_2(x,y);
			move_3(x,y);
			break;
			
		}
	}
	
	static void move_1(int x, int y) {
		if(y<N-1) q.add(new Point(x,y+1,1));
 	}
	static void move_2(int x, int y) {
		if(x<N-1 && y<N-1) {
			if(pipe[x][y+1]!=1 && pipe[x+1][y]!=1)
				q.add(new Point(x+1,y+1,2));
		}
 	}
	static void move_3(int x, int y) {
		if(x<N-1) q.add(new Point(x+1,y,3));
 	}
	
	
	
	static class Point{
		int x; 
		int y;
		int direction;
		
		Point(int x,int y, int direction){
			this.x=x;
			this.y=y;
			this.direction=direction;
		}
	}
	
}

 

 

 

 

2. dp 3차원 배열 이용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;



public class Main_17070_파이프옮기기1 {

	static int N;
	static int[] dx= {0,1,1};
	static int[] dy= {1,0,1};
	static int[][] d;
	static int[][][] dp;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		d=new int[N+1][N+1];
		dp=new int[N+1][N+1][3];
		
		for(int i=1;i<=N;i++) {
			StringTokenizer st=new StringTokenizer(br.readLine());
			for(int j=1;j<=N;j++) {
				d[i][j]=Integer.parseInt(st.nextToken());
			}
		}

		dp[1][2][0]=1;
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
				if(d[i][j]==1) {
					continue;
				}	
				if(d[i][j-1]!=1)
					dp[i][j][0]+=(dp[i][j-1][0]+dp[i][j-1][2]);
				if(d[i-1][j]!=1)	
					dp[i][j][1]+=(dp[i-1][j][1]+dp[i-1][j][2]);
				if(d[i][j-1]==0 && d[i-1][j]==0 && d[i-1][j-1]!=1)  
					dp[i][j][2]+=(dp[i-1][j-1][0]+dp[i-1][j-1][1]+dp[i-1][j-1][2]);
			}
		}
		System.out.println(dp[N][N][0]+dp[N][N][1]+dp[N][N][2]);
	}
}

 

해결하지 못한 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;



public class Main_17070_파이프옮기기 {

	static int N;
	static int[] dx= {0,1,1};
	static int[] dy= {1,0,1};
	static boolean[][] visit;
	static Queue<int[]> q;
	static int[][] d;
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		d=new int[N+1][N+1];
		visit=new boolean[N+1][N+1];
		
		q=new LinkedList<>();
		for(int i=0;i<N;i++) {
			StringTokenizer st=new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				d[i][j]=Integer.parseInt(st.nextToken());
				if(d[i][j]==1) d[i][j]=-1;
			}
		}

		bfs(0,1);
		System.out.println(d[N-1][N-1]);
		
		
	}
	
	static void bfs(int x, int y) {
		
		q.add(new int[] {x,y,1});
		d[x][y]=1;
		
		while(!q.isEmpty()) {

			int[] num=q.poll();
			
			for(int i=0;i<3;i++) {
				if(num[2]==1) {
					if(i==1) continue;
				}
				else if(num[2]==2) {
					if(i==0) continue;
				}
				int nx=num[0]+dx[i];
				int ny=num[1]+dy[i];
				
				if(nx<0 || nx>=N || ny<0 || ny>=N) continue;
				if(d[nx][ny]==-1) continue;
				
				if(i==2 && (d[nx][ny-1]==-1 || d[nx-1][ny]==-1)) continue;
				d[nx][ny]+=1;
				q.add(new int[] {nx,ny,i+1});
			}
		}
	}
}