1520번: 내리막 길
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으
www.acmicpc.net
- 생각
bfs방식을 통해 배열을 돌리면 될 것 같다.
=> 해당 방식으로만 하면 시간초과가 뜬다.
해결방법 : dp배열을 하나 더 만들어서 지나온 길의 값을 저장해 놓는다.
- 코드
실패 코드 : BFS를 통해 queue를 이용하여서 품. 메모리 초과
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
private static int N, M;
private static int[][] array;
private static int count;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
array = new int[M][N];
count = 0;
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0 ; j < N; j++)
array[i][j] = Integer.parseInt(st.nextToken());
}
bfs();
System.out.println(count);
}
private static int[][] xy = {
{1, 0}, {0, 1},
{-1, 0}, {0, -1}
};
private static void bfs() {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] {0,0});
while(!queue.isEmpty()){
int location[] = queue.poll();
// 마지막에 도달하면 count++
if(location[0] == M-1 && location[1] == N-1) {
count++;
continue;
}
for (int[] direction : xy) {
int r = location[0] + direction[0];
int c = location[1] + direction[1];
if(r >= 0 && c >= 0 && r < M && c < N) {
// 값이 작아질때만 queue에 추가
if(array[location[0]][location[1]] > array[r][c]) {
queue.add(new int[] {r,c});
}
}
}
}
}
}
실패 코드2 : queue를 이용하여 돌린 bfs를 재귀형식으로 바꿔줌. 시간 초과
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
private static int N, M;
private static int[][] array;
private static int count;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
array = new int[M][N];
count = 0;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++)
array[i][j] = Integer.parseInt(st.nextToken());
}
bfs(0, 0);
System.out.println(count);
}
// 메모리 초과때문에 메모리 줄이기 위함
private static int[][] xy = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
// 메모리 초과 때문에 bfs를 queue에서 재귀로 바꿈
private static void bfs(int a, int b) {
// base case
if (a == M - 1 && b == N - 1) {
count++;
return;
}
for (int[] direction : xy) {
int r = a + direction[0];
int c = b + direction[1];
if (r >= 0 && c >= 0 && r < M && c < N) {
// 값이 작아질때만 queue에 추가
if (array[a][b] > array[r][c]) {
bfs(r, c);
}
}
}
}
}
성공 코드 : dp배열을 하나 더 만들어서 이미 지나온 길을 가려고 할 시 끝까지 가지않고 전에 저장해 놓은 값을 return 해준다.
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;
public class Main {
private static int N, M;
private static int[][] array, dp;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(bfs(0,0));
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
M = in.nextInt();
N = in.nextInt();
array = new int[M][N];
dp = new int[M][N];
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
array[i][j] = in.nextInt();
dp[i][j] = -1;
}
}
}
// 메모리 초과때문에 메모리 줄이기 위함
private static int[][] xy = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
// 메모리 초과 때문에 bfs를 queue에서 재귀로 바꿈
private static int bfs(int a, int b) {
// base case
if (a == M - 1 && b == N - 1) return 1;
// 이미 지나온 길이면 return으로 해당 index의 값을 리턴해준다. 이렇게 함으로써 왔던길을 가지않아도 됌.
if(dp[a][b] != -1) return dp[a][b];
dp[a][b] = 0;
for (int[] direction : xy) {
int r = a + direction[0];
int c = b + direction[1];
if (r >= 0 && c >= 0 && r < M && c < N) {
// 작아질 때만 재귀로 들어감
if (array[a][b] > array[r][c]) {
// 재귀를 돌면서 해당 index 방향에서 끝까지 도달한 횟수를 누적해서 index에 더 해줌
dp[a][b] += bfs(r, c);
}
}
}
return dp[a][b];
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String readString() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
'algorithm' 카테고리의 다른 글
| [BOJ/JAVA] 백준 2470번 : 두 용액 (0) | 2021.01.28 |
|---|---|
| [BOJ/JAVA] 백준 2178번 : 미로 탐색 (0) | 2021.01.27 |
| [BOJ/JAVA] 백준 7576번 : 토마토 (0) | 2021.01.26 |
| [BOJ/JAVA] 백준 1405번 : 미친 로봇 (0) | 2021.01.26 |
| [BOJ/JAVA] 백준 1477번 : 휴게소 세우기 (0) | 2021.01.25 |