16173 /16174 - 점프왕 쩰리(BFS)

---

16173

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

//백준
public class Main {

	static int size;
	static int[][] array;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		size = sc.nextInt();

		Queue<int[]> q = new LinkedList<>();

		array = new int[size][size];

		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				array[i][j] = sc.nextInt();
			}
		}

		int x = 0;
		int y = 0;
		String result = "Hing";

		q.offer(new int[] { 0, 0 });


			while (!q.isEmpty()) {
				int[] point = q.poll();
				x = point[0];
				y = point[1];
				int add = array[x][y];
				// System.out.println("x: "+x+"y: "+y+"add: "+add);

				if(add==0) {
					//q.poll();
				}
				else if (add == -1) {
					result = "HaruHaru";
					break;
				} else {
					if (x + add < size) {
						q.offer(new int[] { x + add, y });
					}
					if (y + add < size) {
						q.offer(new int[] { x, y + add });
					}

				}

			}
		
		System.out.println(result);



	}

}

KeyPoint: 좌표를 가지고 있어야 하는데 어떻게 가지고 있을지. (이동하고나서 그 이동한 위치에서 출발해야 하기 때문)

큐를 배열로 선언하고 new int[] {0.0} 이렇게 담아주고 꺼내서 썼다.

 

실수한점: 방문여부를 따지지 않았으므로 갔던곳을 또 방문하게 된다 아래의 Large에서 메모리 문제 발생

 

 

 

16174

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 {


	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int size = Integer.parseInt(br.readLine());
		
		StringTokenizer st;
		//StringBuilder sb = new StringBuilder();

		Queue<int[]> q = new LinkedList<>();

		int[][] array = new int[size][size];
		boolean[][] visited = new boolean[size][size];

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


		String result = "Hing";

		q.offer(new int[] { 0, 0 });
		visited[0][0] = true;


			while (!q.isEmpty()) {
				int[] point = q.poll();
				int x = point[0];
				int y = point[1];
				int add = array[x][y];

				// System.out.println("x: "+x+"y: "+y+"add: "+add);

				if(add==0) {
					//q.poll();
				}
				else if (add == -1) {
					result = "HaruHaru";
					break;
				} else {
					if (x + add < size &&visited[x+add][y]==false) {
						q.offer(new int[] { x + add, y });
						visited[x+add][y]=true;
						
					}
					if (y + add < size&&visited[x][y+add]==false) {
						q.offer(new int[] { x, y + add });
						visited[x][y+add]=true;
					}

				}

			}
		
		System.out.println(result);



	}

}

KeyPoint : befferedReader로 바꾸니까 더 진행은 되었지만 결국 방문여부를 따지지 않아 메모리초과가 되었다.

BFS로 풀때에는 방문여부는 필수로 하자.