반응형
Notice
Recent Posts
Recent Comments
Link
지구정복
[BFS,DFS] 이코테 - 미로탈출 본문
728x90
반응형
-자바 dfs, 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 Escape {
private static int n, m; //미로 담을 배열의 행열 크기
private static int[][] arr; //미로 담을 배열(dfs용)
private static int[][] arr1; //미로 담을 배열(bfs용)
//이동할 4방향 정의(상하좌우)
private static int[] dx = {1, -1, 0, 0};
private static int[] dy = {0, 0, 1, -1};
private static int sum = 1;
private static int sum1 = 1;
//dfs함수
private static void dfs( int now_x, int now_y ) {
//현재 노드를 0으로 바꿔서 방문처리한다.
arr[now_x][now_y] = 0;
int x, y;
//상하좌우로 이동하기 위해 arr인덱스값 설정
for( int i=0; i<4; i++ ) {
x = now_x + dx[i];
y = now_y + dy[i];
//x, y값이 배열의 범위를 넘으면 다음 순회
if( x <= 0 || x >= n+1 || y <= 0 || y >= m+1 ) continue;
//배열값이 1이고, x나 y가 기존 x,y보다 클 때만 bfs 재귀적 호출
if( arr[x][y] == 1 && ( x>now_x || y>now_y ) ) {
sum++;
dfs( x, y );
}
}
}//dfs함수 끝
private static void bfs( int now_x, int now_y ) {
//bfs에 사용할 큐 선언
Queue<Integer> que = new LinkedList<Integer>();
//bfs에 담길 x,y좌표를 사용자객체 담아서 큐에 넣는다.
que.add( now_x );
que.add( now_y );
//현재 노드를 0으로 바꿔서 방문처리한다.
arr1[now_x][now_y] = 0;
int x, y;
//큐가 비워질 때까지 반복한다.
while( !que.isEmpty() ) {
now_x = que.poll();
now_y = que.poll();
//현재 노드를 0으로 바꿔서 방문처리한다.
arr1[now_x][now_y] = 0;
for( int i=0; i<4; i++ ) {
x = now_x + dx[i];
y = now_y + dy[i];
//x, y값이 배열의 범위를 넘으면 다음 순회
if( x <= 0 || x >= n+1 || y <= 0 || y >= m+1 ) continue;
//배열값이 1이고, x나 y가 기존 x,y보다 클 때만 아래 코드 실행
if( arr1[x][y] == 1 && ( x>now_x || y>now_y ) ) {
sum1++;
que.add( x );
que.add( y );
}
}
}
}//bfs method end
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
StringTokenizer st = new StringTokenizer( br.readLine() );
n = Integer.parseInt( st.nextToken() ); //미로출구 n행
m = Integer.parseInt( st.nextToken() ); //미로출구 m행
arr = new int[n+1][m+1]; //미로배열 선언
arr1 = new int[n+1][m+1]; //미로배열 선언
for( int i=0; i<=n; i++ ) {
if( i == 0 ) {
int[] tmp = {0, 0, 0, 0, 0, 0, 0};
arr[i] = tmp;
arr1[i] = tmp;
} else {
char[] tmp1 = br.readLine().toCharArray();
for( int j=0; j<=m; j++ ) {
if( j == 0 ) {
arr[i][j] = 0;
arr1[i][j] = 0;
}
else {
arr[i][j] = Character.getNumericValue(tmp1[j-1]);
arr1[i][j] = Character.getNumericValue(tmp1[j-1]);
}
}
}
}
dfs( 1, 1 );
bfs( 1, 1 );
System.out.println( "dfs결과: " + sum );
System.out.println( "bfs결과: " + sum1 );
}//main method end
}
-파이썬 bfs
from collections import deque
n, m = map(int, input().split() )
arr = list()
#2차원 리스트의 맵 정보 입력받기
for i in range(0, n):
arr.append( list( map(int, input() ) ) )
#이동할 4방향 정의(상하좌우)
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def bfs( x, y ):
sum = 1
#현재 배열 값 0으로 바꿔줘서 방문처리
arr[x][y] = 0
#데큐 선언 및 x,y값 추가
que = deque()
que.append( (x, y) )
#큐가 빌 때까지 반복한다.
while que:
#큐의 값 제거
now_x, now_y = que.popleft()
#현재 위치에서 네 방향으로 위치 확인
for i in range( 4 ):
x = now_x + dx[i]
y = now_y + dy[i]
#배열을 벗어나는 값이면 다음 순회
if x < 0 or x >= n or y < 0 or y >= m:
continue
#배열값이1이고, x와 y가 기존의 x, y보다 작은 경우 실행
if arr[x][y] == 1 and ( x > now_x or y > now_y ):
sum += 1
que.append( (x, y) )
return sum
#bfs실행
sum = bfs( 0, 0 )
print( sum )
728x90
반응형
'데이터 엔지니어링 정복 > Algorithm' 카테고리의 다른 글
[BFS,DFS] 백준 - 로또 (0) | 2021.07.07 |
---|---|
[BFS,DFS] 백준 - 연결요소의 개수 (0) | 2021.07.07 |
[BFS,DFS] 이코테 - 음료수 얼려 먹기 (0) | 2021.07.05 |
[BFS,DFS] 백준 - 바닥장식 (0) | 2021.07.05 |
[BFS,DFS] 백준 - 바이러스 (0) | 2021.06.25 |
Comments