BFS
-
BOJ) 벽 부수고 이동하기알고리즘/백준 2020. 7. 23. 15:51
벽 부수고 이동하기 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 풀이 BFS 문제로, (1,1)에서 시작해서 (n,m)에 최소 경로로 도달하기 위해 몇 개의 칸을 밟는지 구하는 문제다. 처음에는 단순하게 visit을 좌표만 체크하면서 (2차원 배열) 답을 구해줬다. 50퍼센트 쯤 넘어갈 때 틀렸다고 뜨는 것을 보고, 벽을 허물고 이동한 경우와 벽을 허물지 않고 이동한 경우가 물린다는 것을 알아챘다. 그래서 visit 변수를 3차원 배열로 생성해주었는데, 벽을 한 번 허물었을 경..
-
BOJ) 나이트의 이동알고리즘/백준 2020. 7. 18. 22:06
나이트의 이동 7562번: 나이트의 이동 문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 www.acmicpc.net 풀이 테스트 케이스의 수가 주어지고, 각 테스트 케이스마다 체스판의 크기, 시작점, 목표 지점이 차례대로 주어진다. 나이트가 시작점을 출발해서 목표 지점에 도달하는 경우의 수를 출력하는 문제다. 나이트가 이동할 수 있는 경우의 수는 8가지다.위의 8가지 경우의 x와 y가 움직이는 위치를 각각 dx와 dy로 선언해줬다.그리고 BFS를 통해서 이미 도착했던 지점인지 visit체크와 함께 움직일 때마다 step을 저장해주면서, 도착지점에 도달하면 ste..
-
BOJ) 적록색약알고리즘/백준 2020. 7. 16. 16:59
적록색약 10026번: 적록색약 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G( www.acmicpc.net 풀이 적록색약이 있는 사람이 봤을 때 영역의 갯수와 일반 사람이 봤을 때 영역의 갯수를 각각 출력하는 문제다. 가장 기본적인 grouping을 활용하는 문제였다. 코드 수를 줄이려면, 서칭하는 메소드를 하나로 합치고 식별 번호를 부여해서 if문을 통해 처리할 수 있다. 하지만, 코드의 길이가 200 300줄이 되는 정도는 아니어서 그냥 나눠서 진행했다. ( solution에서 더 깔끔하게 볼 수 있기 때문에) 평범한 사람이 봤을 때는, 해당 맵과 ..
-
BOJ) 토마토알고리즘/백준 2020. 7. 16. 16:52
토마토 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 세 번을 시도한 끝에 풀었다. 처음에는 익지 않은 토마토의 총 갯수를 입력받을 때 저장하고, 매 회차 익지않은 토마토 주변을 탐색하면서 익게 만들었다. 하지만, 당연하게도 시간초과가 떴다. 두번째로는 익지 않은 토마토에서 시작하는 방법을 그대로 적용하고, 각 토마토 위치마다 익게되는 날짜를 저장할 int형 배열을 만들었다. BFS 탐색을 통해서 저장한 다음, 최대 날짜를 최신화했고, 안익은 토마토가 0일로 남아있다면 불가능하다..
-
BOJ) 유기농 배추알고리즘/백준 2020. 7. 8. 19:53
유기농 배추 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net 풀이 이 문제도 grouping 문제여서, find-union을 써볼까 했지만, 크게 효율적일 것 같다는 느낌이 없었고, 이 문제에 적용하기에는 조금 복잡해질 것 같다고 생각했다. 그래서 그냥 BFS로 풀었다.. ㅎㅎㅎ 총 세번을 제출했고, BFS, BFS, DFS 순으로 제출했다. 첫번째는 평소에 풀던 것 처럼 grouping을 해주면서, gourping이 끝난 이후 저장된 groupIdx를 출력해줬다. 하지만, group을 지어서 값을 변경하거나 이용하지..
-
BOJ) 인구 이동알고리즘/백준 2020. 7. 7. 20:28
인구 이동 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모�� www.acmicpc.net 풀이 인접해있는 땅과 인구의 차이가 주어진 L과 R 사이에 존재하면 평균을 내면서, L과 R 사이에 존재하지 않을 때 까지 묶어주는 문제다. 처음 제출하자마자 맞았지만, 효율성이 조금 떨어진다고 생각해서 코드를 수정했다. 얼마 전 포스팅했던 성곽 문제랑 푸는 방법이 비슷하다. grouping을 해주고 각 group의 평균 값을 HashMap에 저장한다. 전체 grouping이 끝나면, 각 gourp마다 평균 값을 넣어주면서 조건에 부합..
-
BOJ) 성곽알고리즘/백준 2020. 7. 6. 18:18
성곽 2234번: 성곽 문제 대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로� www.acmicpc.net 풀이 생각보다 코드가 길어진 문제다. 각 방에 대해 상하좌우에 벽이 있는지 없는지를 int형 숫자로 주어진다. 이 숫자는 각각 벽이 있다는 의미를 가진 2진수 숫자를 모두 더한 값이다. 벽의 방향 숫자 서 1 북 2 동 4 남 8 위의 벽 정보에 따라서 map의 숫자가 정해진다. 만약 서쪽과 북쪽에 벽이 있다면, 해당 방의 숫자는 3으로 주어지고, 동쪽과 남쪽은 12가 주어지는 식이었다. 그래서, 거추장스럽지만 0~15까지 움직일 수 있는 방향을 미리 저장했다. (..
-
BOJ) 벽 부수고 이동하기 4알고리즘/백준 2020. 7. 3. 16:37
벽 부수고 이동하기 4 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 � www.acmicpc.net 풀이 처음에는 모든 벽에 대해서 벽을 허물고 값을 구하고자 했다. 하지만, 주어진 n과 m의 최대값이 1000이나 되기 때문에 시간초과가 뜰 것 같았다. 그래서 생각한 것은 0에 대해서 grouping을 해주는 것이다. 빈칸이 이어진 곳들에 대해서 그룹 index를 남기고, 몇 개의 빈칸이 존재하는지 세주어서 저장하는 것이다. 이후에, Map을 돌면서 벽을 허물었을 경우, 상하좌우에 (인접한 곳에) 빈칸 그룹이 가지..