BFS
-
BOJ 16985번 Maaaaaaaaaze 문제 자바(java) 풀이 난이도: 골드3 BOJ 16985번 Maaaaaaaaaze 문제정리 3차원 미로 탈출 대회 개최 5x5 크기의 판이 5개 주어진다. 하얀색 칸은 참가자가 들어갈 수 있는 칸, 검은 칸은 못들어가는 칸이다. 참가자는 주어진 판들을 시계 or 반시계 방향으로 자유롭게 회전할 수 있다. 뒤집을 수는 없다. 회전을 완료한 후 참가자는 판 5개를 쌓는다. 쌓는 순서는 참가자 마음대로 한다. 입구는 참가자가 임의로 선택한 꼭지점. 출구는 입구와 면을 공유하지 않는 꼭짓점 참가자 중에서 본인이 설계한 미로를 가장 적은 이동 횟수로 탈출한 사람이 승리한다. 입구에서 출구로 도달할 수 있는 방법이 없는 경우 탈출이 불가능 하다. 문제 풀이 이 문제는 ..
[BFS, 순열] 16985번 Maaaaaaaaaze 자바(java) 풀이BOJ 16985번 Maaaaaaaaaze 문제 자바(java) 풀이 난이도: 골드3 BOJ 16985번 Maaaaaaaaaze 문제정리 3차원 미로 탈출 대회 개최 5x5 크기의 판이 5개 주어진다. 하얀색 칸은 참가자가 들어갈 수 있는 칸, 검은 칸은 못들어가는 칸이다. 참가자는 주어진 판들을 시계 or 반시계 방향으로 자유롭게 회전할 수 있다. 뒤집을 수는 없다. 회전을 완료한 후 참가자는 판 5개를 쌓는다. 쌓는 순서는 참가자 마음대로 한다. 입구는 참가자가 임의로 선택한 꼭지점. 출구는 입구와 면을 공유하지 않는 꼭짓점 참가자 중에서 본인이 설계한 미로를 가장 적은 이동 횟수로 탈출한 사람이 승리한다. 입구에서 출구로 도달할 수 있는 방법이 없는 경우 탈출이 불가능 하다. 문제 풀이 이 문제는 ..
2020.04.01 -
BOJ 5427번 불 문제 자바(java) 풀이 랭크 : 골드4 백준 5427번 불 문제 정리 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있고, 불이 번져서 출구를 향해 뛰고 있다. 매 초마다 불은 동서남북 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있다. 이동하는데 1초가 걸린다. 상근이는 벽이 있거나 불이 번졌으면 갈 수 없다. 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다!!!! 문자 #: 벽 .: 지나갈 수 있는 공간 @: 상근이의 미로에서의 초기위치(지나갈 수 있는 공간) *: 불이난 공간 불이 도달하기 전에 미로를 탈출할 수 없는 경우 'IMPOSSIBLE' 출력 탈출할 수 있는 경우 가장 빠른 탈출시간 출력 문제..
[BFS] 백준 5427, 4179번 불(Fire) 문제 자바(java) 풀이BOJ 5427번 불 문제 자바(java) 풀이 랭크 : 골드4 백준 5427번 불 문제 정리 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있고, 불이 번져서 출구를 향해 뛰고 있다. 매 초마다 불은 동서남북 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있다. 이동하는데 1초가 걸린다. 상근이는 벽이 있거나 불이 번졌으면 갈 수 없다. 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다!!!! 문자 #: 벽 .: 지나갈 수 있는 공간 @: 상근이의 미로에서의 초기위치(지나갈 수 있는 공간) *: 불이난 공간 불이 도달하기 전에 미로를 탈출할 수 없는 경우 'IMPOSSIBLE' 출력 탈출할 수 있는 경우 가장 빠른 탈출시간 출력 문제..
2020.03.28 -
BOJ 2583번 영역 구하기 문제 자바(java) 풀이 난이도: 실버1 풀이시간: 30분 백준 2583번 영역 구하기 문제정리 MxN 크기의 모눈종이가 주어진다. 모눈 종이 위에 K개의 직사각형을 그린다. k개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 몇개의 영역으로 분리되는지, 각 영역의 넓이는 어떤지 구하여라 문제풀이 분리된 영역과 넓이를 구하는 것이므로 모든 좌표에서 bfs 탐색을 하면 됩니다. 이 문제는 영역을 구분짓는 문제인 보물섬, 치즈, 빙산과 유사합니다. 문제에서 주어지는 직사각형의 좌표들과 배열의 인덱스가 다르기 때문에 주어진 x,y좌표를 반대로 바꿔줍니다. ( 바꾸면 답이 잘 나오는지 직접 그려보느라 시간 좀더 걸림 ) 직사각형이 있는 곳은 map..
[BOJ] 백준 2583번 영역 구하기 자바(java) 풀이 (dfs, bfs)BOJ 2583번 영역 구하기 문제 자바(java) 풀이 난이도: 실버1 풀이시간: 30분 백준 2583번 영역 구하기 문제정리 MxN 크기의 모눈종이가 주어진다. 모눈 종이 위에 K개의 직사각형을 그린다. k개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 몇개의 영역으로 분리되는지, 각 영역의 넓이는 어떤지 구하여라 문제풀이 분리된 영역과 넓이를 구하는 것이므로 모든 좌표에서 bfs 탐색을 하면 됩니다. 이 문제는 영역을 구분짓는 문제인 보물섬, 치즈, 빙산과 유사합니다. 문제에서 주어지는 직사각형의 좌표들과 배열의 인덱스가 다르기 때문에 주어진 x,y좌표를 반대로 바꿔줍니다. ( 바꾸면 답이 잘 나오는지 직접 그려보느라 시간 좀더 걸림 ) 직사각형이 있는 곳은 map..
2020.03.12 -
BOJ 7576번 토마토 문제 자바(java) 풀이 난이도: 실버1 백준 7576번 토마토 문제정리 보관 후 하루가 지나면 익은 토마토에 인접한 익지 않은 토마토가 익게된다. 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 를 의미한다. 대각선 토마토에는 영향을 줄 수 없다. 모든 토마토가 익는데 필요한 최소 일 수를 구해라 토마토가 없는 칸이 있을 수 있다. 처음부터 토마토 모두가 익어있다면 0, 모두 익을 수 없다면 -1 출력 토마토 상태 1 : 익은 토마토 0 : 익지 않은 토마토 1 : 토마토 없음 문제 풀이 최소 시간을 구해야 하므로 모든 방향으로 퍼져가며 토마토를 익게 해나가며 구해야한다. 즉 bfs를 이용하여 탐색합니다. 익은 토마토가 여러개인 경우도 있기 때문에 익은 토마토를 모두 list에 담고 b..
[BOJ] 백준 7576번 토마토 자바(java) 풀이 (bfs)BOJ 7576번 토마토 문제 자바(java) 풀이 난이도: 실버1 백준 7576번 토마토 문제정리 보관 후 하루가 지나면 익은 토마토에 인접한 익지 않은 토마토가 익게된다. 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 를 의미한다. 대각선 토마토에는 영향을 줄 수 없다. 모든 토마토가 익는데 필요한 최소 일 수를 구해라 토마토가 없는 칸이 있을 수 있다. 처음부터 토마토 모두가 익어있다면 0, 모두 익을 수 없다면 -1 출력 토마토 상태 1 : 익은 토마토 0 : 익지 않은 토마토 1 : 토마토 없음 문제 풀이 최소 시간을 구해야 하므로 모든 방향으로 퍼져가며 토마토를 익게 해나가며 구해야한다. 즉 bfs를 이용하여 탐색합니다. 익은 토마토가 여러개인 경우도 있기 때문에 익은 토마토를 모두 list에 담고 b..
2020.03.11 -
sw expert academy 1953번 탈주범 검거 자바(java) 풀이 모의 SW 역량 테스트 풀이시간: 1시간 30분 sw expert academy 1953번 탈주범 검거 문제정리 탈주범은 탈출한지 1시간 뒤 지하터널의 어느 지점으로 들어갔다. 터널끼리 연결 되어있는 경우 이동이 가능하다. 탈주범은 시간당 1의 거리를 이동할 수 있다. 지하터널은 총 7종류의 구조물로 구성되어 있다. 터널이 없는 장소(구조물 X) 상하좌우 연결 상하 연결 좌우 연결 상우 연결 하우 연결 하좌 연결 상좌 연결 문제풀이 이 문제는 dfs가 아닌 bfs를 이용해야 풀 수 있습니다. 시간안에 해결하거나 최단 거리등과 관련된 문제는 bfs 탐색이 좋습니다. 시간에 얼마나 퍼져서 갈 수 있는지를 묻는 문제이기 때문에 bfs..
[SWEA] 모의 sw 역량 테스트 :: 1953번 탈주범 검거 (bfs, 비트 연산)sw expert academy 1953번 탈주범 검거 자바(java) 풀이 모의 SW 역량 테스트 풀이시간: 1시간 30분 sw expert academy 1953번 탈주범 검거 문제정리 탈주범은 탈출한지 1시간 뒤 지하터널의 어느 지점으로 들어갔다. 터널끼리 연결 되어있는 경우 이동이 가능하다. 탈주범은 시간당 1의 거리를 이동할 수 있다. 지하터널은 총 7종류의 구조물로 구성되어 있다. 터널이 없는 장소(구조물 X) 상하좌우 연결 상하 연결 좌우 연결 상우 연결 하우 연결 하좌 연결 상좌 연결 문제풀이 이 문제는 dfs가 아닌 bfs를 이용해야 풀 수 있습니다. 시간안에 해결하거나 최단 거리등과 관련된 문제는 bfs 탐색이 좋습니다. 시간에 얼마나 퍼져서 갈 수 있는지를 묻는 문제이기 때문에 bfs..
2020.03.08 -
BOJ 1260번 DFS BFS 자바(java) 풀이 랭크 : 실버1 백준 온라인 저지(BOJ) 1260 DFS BFS 문제 자바 풀이 백준 1260 DFS BFS 문제 문제정리 N M V(정점의 개수, 간선의 수, 시작할 정점 번호) 연결 정보들이 주어진다. 그래프 정보들을 가지고 dfs와 bfs로 순회하여 순서대로 출력하기 문제풀이 이 문제는 정점의 연결 상태를 적절한 자료형으로 저장하여 그래프를 탐색하는 문제입니다. 저는 그래프의 연결 상태를 인접 그래프(adjancy graph)형태로 저장하여 탐색하였습니다. 인접 행렬 다음과 같은 인접 행렬가 주어졌습니다. 무엇을 나타내는 걸까요?? 010 101 010 adj[i][j] = 1 이라면 점 i와 j는 연결되어 있다. 0이면 연결되어 있지 않다. ..
BOJ 1260번 DFS BFS 문제 자바 풀이BOJ 1260번 DFS BFS 자바(java) 풀이 랭크 : 실버1 백준 온라인 저지(BOJ) 1260 DFS BFS 문제 자바 풀이 백준 1260 DFS BFS 문제 문제정리 N M V(정점의 개수, 간선의 수, 시작할 정점 번호) 연결 정보들이 주어진다. 그래프 정보들을 가지고 dfs와 bfs로 순회하여 순서대로 출력하기 문제풀이 이 문제는 정점의 연결 상태를 적절한 자료형으로 저장하여 그래프를 탐색하는 문제입니다. 저는 그래프의 연결 상태를 인접 그래프(adjancy graph)형태로 저장하여 탐색하였습니다. 인접 행렬 다음과 같은 인접 행렬가 주어졌습니다. 무엇을 나타내는 걸까요?? 010 101 010 adj[i][j] = 1 이라면 점 i와 j는 연결되어 있다. 0이면 연결되어 있지 않다. ..
2020.02.24