지구정복

[BFS,DFS] 백준 - 점프왕쩰리 본문

데이터 엔지니어링 정복/Algorithm

[BFS,DFS] 백준 - 점프왕쩰리

eeaarrtthh 2021. 6. 25. 11:57
728x90
반응형

-문제

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

 

 

-자바(dfs)

package bfs_dfs;

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 Jelly1 {
	private static BufferedWriter bw = new BufferedWriter( new OutputStreamWriter( System.out ) );
	
	private static int dr[] = {1, 0};
	private static int dc[] = {0, 1};
	
	//dfs 선언
	private static void dfs(int n, int[][] arr, boolean[][] visit, int a, int b ) throws IOException {
		int now = arr[a][b];
		
		//-1에 도달했으면 결과 출력하고 종료
		if( now == -1 ) {
			bw.write( "HaruHaru" );
			bw.flush();
			System.exit(0);
		} 
		
		//오른쪽 혹은 아래로 가야하므로 2회 반복
		for( int i=0; i<2; i++ ) {
			int row = a + dr[i]*now;	//i 0일때는 row값만 변경되고 col값은 그대로
			int col = b + dc[i]*now;	//i 1일때는 col값만 변경되고 row값은 그대로
			
			//row와 col이 이상치이면 continue
			if( row < 0 || col < 0 || row >= n || col >= n ) continue;
			//visit가 true면 방문했으므로 continue
			if( visit[row][col] ) continue;
			
			//방문하지 않은 노드면 true
			visit[row][col] = true;
			dfs( n, arr, visit, row, col );
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		StringTokenizer st;
		
		//게임 구역의 크기 입력받기
		int n = Integer.parseInt( br.readLine() );
		
		int[][] arr = new int[n][n];	//게임판 구역 배열
		boolean[][] visit = new boolean[n][n];	//노드 방문여부 배열
		
		//게임판의 구역 입력받기
		for(int i=0; i<n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( int j=0; j<n; j++ ) {
				arr[i][j] = Integer.parseInt( st.nextToken() );
			}
		}
		
		//dfs함수 호출
		dfs(n, arr, visit, 0, 0);
		
		//dfs함수에서 HaruHaru 나오지않으면 Hing출력
		bw.write( "Hing" );
		bw.flush();
	}
	
}

 

-자바(bfs)

package bfs_dfs;

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 BJ16173 {
    static int n;
    static int[][] map;
    static boolean[][] visit;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt( br.readLine() );
        map = new int[n][n];
        visit = new boolean[n][n];

        StringTokenizer st;
        for( int i=0; i<n; i++ ) {
            st = new StringTokenizer( br.readLine() );
            for( int j=0; j<n; j++ ) {
                map[i][j] = Integer.parseInt( st.nextToken() );
            }
        }

        System.out.println( bfs() );
    }

    static String bfs() {
        Queue<Geo> que = new LinkedList<Geo>();
        que.add( new Geo(0, 0) );
        visit[0][0] = true;

        while( !que.isEmpty() ) {
            Geo tmp_geo = que.poll();
            int cur_x = tmp_geo.x;
            int cur_y = tmp_geo.y;

            //만약 큐에서 뺀 값의 좌표가 목표하는 좌표의 값(-1)이 나오면 종료
            if( map[cur_x][cur_y] == -1 ) return "HaruHaru";
            
            for( int i=0; i<2; i++ ) {
                int new_x, new_y;
                if( i==0 ) {//x값 증가
                    new_x = cur_x + map[cur_x][cur_y];
                    new_y = cur_y;
                } else {    //y값 증가
                    new_x = cur_x;
                    new_y = cur_y + map[cur_x][cur_y];
                }

                if( new_x<0 || new_x>=n || new_y<0 || new_y>=n ) continue;
                if( visit[new_x][new_y] ) continue;

                que.add( new Geo( new_x, new_y ) );
                visit[new_x][new_y] = true;
                
            }
        }

        //위 큐를 전부 비워졌는데도 return이 안되었으면 목표지점에 도착하지 못한 것
        return "Hing";
    }
}

class Geo {
    int x;
    int y;

    public Geo( int x, int y ) {
        this.x = x;
        this.y = y;
    }
}

 

 

728x90
반응형
Comments