[Java, Python] 2589 보물섬 - BFS
https://www.acmicpc.net/problem/2589
2589번: 보물섬
첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의
www.acmicpc.net
[Python] - 시간초과 Code -> 오잉?????pypy3으로 돌리니까 맞음 ㄷ ㄷㄷㄷㄷ
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
from collections import deque
from sys import stdin
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def bfs(x, y):
queue.append([x, y])
visit = [[0]*C for _ in range(R)]
visit[x][y] = 1
num = 0
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < R and 0 <= ny < C and arr[nx][ny] == 'L' and visit[nx][ny] == 0:
visit[nx][ny] = visit[x][y] + 1
num = max(num, visit[nx][ny])
queue.append([nx, ny])
return num-1
R, C = map(int, input().split())
arr = [list(map(str, stdin.readline())) for _ in range(R)]
queue = deque()
cnt = 0
for r in range(R):
for c in range(C):
if arr[r][c] == 'L':
cnt = max(cnt, bfs(r, c))
print(cnt)
|
cs |
맞는데,,, 맞는데 시간초과가 남...... ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅜㅠㅜㅜㅠㅜㅜㅜㅜㅜㅠㅜㅠㅜ
뭔짓을 해도 안줄어든다.
질문 검색 찾아보니까 L개수를 세서 jump하면 된다 이런 말이 있던데 나중에 꼭 시도해보겠다...
흑
*************
pypy3으로 제출하고 성공!
지금까지는 그런적이 없었는데, 주위에 물어보니 python3에서 시간초과 에러가 뜨는 것들을 pypy3으로 제출하면 답안인 경우가 있다고 한다.
[Java] - Correct Code
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
//아무리봐도 BFS!
public class Main {
static char[][] map;
static int[][] cnt;
static boolean[][] visit;
static int R;
static int C;
static int result;
static int[][] del = {{0,1},{1,0},{0,-1},{-1,0}};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] tmp = br.readLine().split(" ");
R = Integer.parseInt(tmp[0]);
C = Integer.parseInt(tmp[1]);
map = new char[R+1][C+1];
for(int r=1;r<=R;r++){
String tmp2 = br.readLine();
for(int c=1;c<=C;c++){
map[r][c]= tmp2.charAt(c-1);
}
}
result =0;
for(int r=1;r<=R;r++){
for(int c=1;c<=C;c++){
if(map[r][c] == 'L'){
BFS(r, c);
}
}
}
System.out.println(result);
}
public static void BFS(int x, int y){
visit = new boolean[R+1][C+1];
cnt = new int[R+1][C+1];
Queue<xy> queue = new LinkedList<>();
queue.offer(new xy(x, y)); //x,y를 큐에 삽입
visit[x][y] = true;
while(!queue.isEmpty()){
int c_x = queue.peek().x; //queue에서 x,y 저장.
int c_y = queue.peek().y;
queue.poll(); //queue에서 제거
for(int i=0;i<4;i++){
int n_x = c_x + del[i][0];
int n_y = c_y + del[i][1];
if(isIn(n_x, n_y)){
queue.offer(new xy(n_x, n_y));
visit[n_x][n_y] = true;
cnt[n_x][n_y] = cnt[c_x][c_y] +1;
if(result < cnt[n_x][n_y]) result = cnt[n_x][n_y];
}
}
}
}
static boolean isIn(int r, int c){
return 0<r && 0<c && r<=R && c<=C && map[r][c] == 'L' && !visit[r][c];
}
public static class xy{
int x, y ;//좌표를 저장
xy(int x, int y){
this.x = x;
this.y = y;
}
}
}
|
cs |
Python풀다가 짜증나고 Java풀다가 재밌었기는 처음이다. 헿
먼저... 현재 내 위치랑 연결된 좌표들을 따라가며 카운트를 한다는 점에서 BFS라는 생각이 들었다.
BFS라면 큐를 이용하는 자료구조 이므로 자바에서 큐를 사용하는 방법을 먼저 공부했다 !!
| python | java |
| append([a,b]) | offer({a,b}) |
| popleft() | poll() |
| queue = deque() | Queue<xy> queue = new LinkedList<>(); |
| 정도만 사용해보았다. |
Python에서 queue에 2차원 배열을 삽입할 때는 언제나 list형태로 묶어서 삽입하곤 했다.
그런데 Java에서 queue를 구현할 때는 배열보다는 LinkedList형태를 쓰는게 더 쉽고, 대중적이라고 한다.
데이터들을 하나의 객체에 담고 (내 코드에서는 xy라는 객체로 만들어줌) 이어주면 되기 때문에 삽입, 제거, 연결 등등에서 관리가 편하다고 한다.
Queue는 선입선출이므로, 항상 첫 번째로 저장된 데이터를 삭제한다.
이 때 ArrayList와 같은 배열 기반 자료구조를 사용하게 되면, 빈공간을 채우기 위해서 데이터의 복사가 발생하므로 매우 비효율적이다.
따라서 ArrayList보다 데이터의 삽입, 제거가 쉬운 LinkedList로 구현한다고 한다. 내 윈도우에서는 속도가 만배 차이가 났다.ㅋㅋㅋ
| method | ArrayList | LinkedList |
| add() | O(1) | O(1) |
| add(idx, val) | O(N) | O(1) |
| remove(idx) | O(N) | O(1) |
| remove(val) | O(N) | O(1) |
| get(idx) | O(1) | O(N) |
| indexOf(val) | O(N) | O(N) |
** 추가 **
오늘 수업에서도 LinkedList -> Deque -> Queue 라고 하신걸 보니 정말 linkedlist를 사용하는 것이 대다수인듯!!
[구현]
간단한 BFS 기본 문제였다.
보물섬 지도map을 돌면서 그 값이 'L'라면, BFS를 돌린다. 상하좌우로 돌리면서 연결된 모든 정점을 지나간다. 이 때 연결된 정점을 지날 때는 isIn()을 통해 범위를 벗어나지 않고, 방문하지 않았으면서 값이 'L'인 곳만을 탐색하게 조건을 걸어주었고,
미리 초기화해놓은 cnt값이 한번 칸을 이동할 때마다 증가하도록 하였다.
만약 해당 노드에서의 최대값이 result 값보다 크다면, resul값을 덮어씌우도록 하였다.
알고리즘은 python의 BFS와 거의 비슷하지만 단 하나 달랐던 점이 있다면 새로운 객체를 queue에 집어넣어주었다는 것 !!
자바를 이용한 BFS의 특징인 것 같다. 이 부분만 다르다.
끄읕