[백준/java] 9205. 맥주 마시면서 걸어가기

문제 링크 - https://www.acmicpc.net/problem/9205

🌱 문제

🌱 풀이

처음에 시도한 방법

• 맥주가 50미터 마다 1병 필요하고, 장소이 좌표가 (두 값 모두 미터, -32768 ≤ x, y ≤ 32767) 와 같으므로 삼만x삼만 배열에는 나타낼 수 없겠다고 생각했다.
• 그래서 좌표값을 50으로 나누고 각각의 좌표에 655를 더해준 후 (음수 값일수 있으니) bfs를 돌리는 방법을 시도해보았다. bfs를 돌리면서 맨허튼 거리가 20이하이면(앞에서 50으로 나눴으니까) dist= dist+1로 갱신하고, 방문체크를 하고 queue에 넣는 일반적인 방식으로 풀려고 했다.
• 그러나 메모리 초과가 떴다. 생각해보니, 이 방법으로 진행하면 visit[][] , dist[][] 배열 모두 약 1312x1312 크기로 선언해야 했고, 최악(?)의 경우 queue에 약 100만개의 좌표(Point)를 add해줘야하기 때문에 메모리 초과가 난것 같다. (물론 시간초과도 날지도)

다시 시도한 방법

• 배열 자체에 출발지점,도착지점,편의점을 저장하지 않고 ArrayList<Point>에 편의점 좌표들을 담아놓았다. (시작지점, 도착지점은 변수로 따로 기억)
• 출발지점부터 bfs를 시작하고, 편의점 리스트를 돌면서 갈 수 있는 지점은 방문체크 후 queue에 담았다.
• 또한 queue에서 좌표를 하나 꺼낼때마다 그 지점에서 도착지점까지 갈 수 있는지를 검사하여 갈 수 있으면 answer="happy"로 갱신하고 bfs를 종료해주었다. 이렇게 하면 현재 좌표가 집이던 다른 편의점이던 도착지점에 갈 수 있는 즉시 바로 bfs를 종료하게 된다.

🌱 실패 코드 (메모리 초과)

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

// 9205. 맥주 마시면서 걸어가기 	
public class Main {

	static class Point {
		int r, c;

		public Point(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	static int TC, N;
	static int arr[][];
	static int dist[][];
	static boolean visited[][];
	static int dr[] = { -1, 1, 0, 0 };
	static int dc[] = { 0, 0, -1, 1 };
	static String answer;

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

		for (int t = 1; t <= TC; t++) {
			N = Integer.parseInt(br.readLine());
			arr = new int[1312][1312];
			visited = new boolean[1312][1312];
			dist=new int[1312][1312];
			Queue<Point> q = new ArrayDeque<Point>();
			answer="sad";

			for (int i = 0; i < N + 2; i++) {

				st = new StringTokenizer(br.readLine());
				int c = Integer.parseInt(st.nextToken());
				int r = Integer.parseInt(st.nextToken());
				c = (c + 32768);
				if (c % 50 == 0)
					c = c / 50;
				else
					c = c / 50 + 1;

				r = (r + 32768);
				if (r % 50 == 0)
					r = r / 50;
				else
					r = r / 50 + 1;

				if (i == 0) { // 집
					arr[r][c] = 1;
					q.add(new Point(r, c));
					visited[r][c] = true;
				}
				if (i > 0 && i < N + 1) { // 편의점
					arr[r][c] = 1;
				} else { // 도착지점
					arr[r][c] = 2;
				}
			}

			// bfs
			loop:
			while (!q.isEmpty()) {
				Point cur = q.poll();

				for (int d = 0; d < 4; d++) {
					int nr = cur.r + dr[d];
					int nc = cur.c + dc[d];

					if (nr >= 0 && nc >= 0 && nr < 1312 && nc < 1312 && visited[nr][nc]==false) {
						if (dist[cur.r][cur.c] == 20) // 더이상 못감 
							continue;
						visited[nr][nc]=true;
						dist[nr][nc]=dist[cur.r][cur.c]+1;
						if(arr[nr][nc]==1)
							dist[nr][nc]=0;
					
						q.add(new Point(nr,nc));
						
						if(arr[nr][nc]==2) {
							answer="happy";
							break loop;
						}
					}
				}
			}
			System.out.println(answer);
		}
	}
}

🌱 정답 코드

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

// 9205. 맥주 마시면서 걸어가기 	
public class boj_9205 {

	static class Point {
		int r, c;

		public Point(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	static int TC, N;
	static boolean visited[];
	static int dr[] = { -1, 1, 0, 0 };
	static int dc[] = { 0, 0, -1, 1 };
	static String answer;

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

		for (int t = 1; t <= TC; t++) {
			N = Integer.parseInt(br.readLine());
			ArrayList<Point> stores = new ArrayList<Point>();
			Queue<Point> q = new ArrayDeque<Point>();
			visited = new boolean[N];
			answer = "sad";

			st = new StringTokenizer(br.readLine());
			int startC = Integer.parseInt(st.nextToken());
			int startR = Integer.parseInt(st.nextToken());
			// 집 좌표 q에 넣기
			q.add(new Point(startR, startC));

			// 편의점 좌표 리스트에 넣기
			for (int i = 0; i < N; i++) {

				st = new StringTokenizer(br.readLine());
				int c = Integer.parseInt(st.nextToken());
				int r = Integer.parseInt(st.nextToken());
				stores.add(new Point(r, c));
			}
			st = new StringTokenizer(br.readLine());
			int endC = Integer.parseInt(st.nextToken());
			int endR = Integer.parseInt(st.nextToken());

			// bfs
			while (!q.isEmpty()) {
				Point cur = q.poll();
				
				// 현재 지점 (집 or 편의점) 에서 도착지점까지 갈수있으면 answer 설정 후 break 
				if (Math.abs(cur.r - endR) + Math.abs(cur.c - endC) <= 1000) {
					answer = "happy";
					break;
				}
				
				for (int i = 0; i < stores.size(); i++) {
					Point next = stores.get(i);
					
					//이미 방문한 편의점이면 패스 
					if(visited[i]) continue;
					
					//다음 편의점이  현재 지점(집 or 편의점)에서 갈수 있는 거리이면 방문체크하고 queue에 담기 
					if(Math.abs(cur.r-next.r)+Math.abs(cur.c-next.c)<=1000) {
						visited[i]=true;
						q.add(new Point(next.r, next.c));
					}
				}

			}
			System.out.println(answer);

		}
	}

}