본문 바로가기

알고리즘 문제/백준81

[백준] 2178번: 미로 탐색 💡문제 분석 요약N x M 크기의 미로에서 (1, 1)에서 (N, M)까지 이동하는데 필요한 최소의 칸 수를 구하는 문제이다.시간 제한: 1초메모리 제한: 192MB 💡알고리즘 설계줄의 개수 N, 칸의 개수 M 를 입력받고, (N, M)의 미로 정보를 입력받는다.BFS 메서드를 호출하여 미로를 탐색한다.BFS 메서드`Queue` 타입의 큐를 생성한다. (탐색할 좌표를 저장함)시작 위치 (1, 1)를 큐에 넣는다.큐가 빌 때까지:큐의 맨 앞의 값을 꺼낸다. ⇒ 현재 위치 (`cur`)`cur`의 상하좌우를 탐색한다.탐색 위치 (x, y)가 미로의 범위에 속하고, 이동 가능한 경로 (`graph[x][y] = 1`)일 경우해당 위치를 큐에 넣는다.해당 위치를 방문 처리한다. (`graph[x][y] = .. 2024. 7. 20.
[백준] 1697번: 숨바꼭질 💡문제 분석 요약수빈의 위치를 N, 동생의 위치를 K로 입력받는다. 수빈의 위치를 X라고 할 때 X-1, X+1, 2*X로 이동할 수 있고, 이동할 경우 1초가 소요된다. 이 때 수빈이 동생을 찾을 수 있는 가장 빠른 시간을 구하는 문제이다.시간 제한: 2초메모리 제한: 128MB 💡알고리즘 설계수빈의 위치 `n` 과 동생의 위치 `k` 를 입력받는다.위치에 따른 이동 시간을 저장하는 `time`배열을 생성한다. (0 초기화)`time`배열의 값이 0일 경우 방문하지 않은 것으로 처리한다. (= 이동 시간이 0)`time[n]` 을 1로 설정하고, BFS를 이용해 `k`위치까지의 이동 시간을 계산한다.BFS 메서드시작 위치를 큐에 넣는다.큐가 빌 때까지:큐의 맨 앞의 값을 가져온다. ⇒ 현재 위치 `.. 2024. 7. 19.
[백준] 1012번: 유기농 배추 💡문제 분석 요약배추를 심은 배추밭의 정보를 입력받아, 배추가 모여있는 곳이 몇 군데인지(최소의 배추흰지렁이 수) 출력하는 문제이다.시간 제한: 1초메모리 제한: 512MB 💡알고리즘 설계`boolean[][] land` 에 배추가 있는 경우 true, 없는 경우 false로 설정한다.`land` 를 순회하며 배추가 있을 경우해당 위치를 false로 설정하고 `count` 를 증가시킨다.해당 위치로 dfs 메서드를 호출한다.dfs 메서드해당 위치의 상하좌우를 순회하여 배추가 있을 경우해당 위치를 false로 설정한다.해당 위치로 dfs 메서드를 재귀 호출한다. 💡코드import java.io.*;public class Main { static boolean[][] land; static .. 2024. 7. 18.
[백준] 11724번: 연결 요소의 개수 💡문제 분석 요약방향없는 그래프의 간선 정보를 입력받아, 연결 요소를 출력하는 문제이다.시간 제한: 3초메모리 제한: 512MB 💡알고리즘 설계boolean[][] graph 에 그래프 간선 정보를 저장한다. (양방향)모든 정점을 순회하며 방문 여부 검사해당 정점을 방문하지 않은 경우 (visited[i] = false)dfs 메서드 호출한다.연결 요소 개수(count)를 증가시킨다.dfs 메서드현재 정점을 방문 처리한다.해당 정점과 연결된 정점이 아직 방문하지 않은 경우 (graph[index][i] && !visited[i])해당 정점을 재귀적으로 dfs 호출한다. 💡코드import java.io.*;public class Main { static int n, k; static boo.. 2024. 7. 17.
[백준] 2667번: 단지번호붙이기 💡문제 분석 요약주어진 지도 정보를 통해 연결된 집들의 단지를 찾아 단지 수와 각 단지 내 집의 수를 오름차순으로 출력하는 문제이다.시간 제한: 1초메모리 제한: 128MB 💡알고리즘 설계`int[n][n] house` 에 지도 정보를 저장한다.`house` 의 모든 위치를 반복집이 존재하고 방문하지 않은 경우 (`house[i][j] == 1 && !visited[i][j]`)단지 수(`count`)를 1 증가시키고, 단지 내 집의 수(`house_count`)를 1로 초기화한다.해당 위치을 방문 처리한다. (`visited[i][j] = true`)dfs 함수를 호출해 해당 위치의 상하좌우 집을 검사한다.`house_counts`에 현재 단지내 집의 수를 추가한다.dfs 함수현재 집의 상하좌우를 .. 2024. 7. 16.
[백준] 1260번: DFS와 BFS 💡문제 분석 요약입력받은 그래프의 정보를 DFS와 BFS로 탐색한 결과를 출력하는 문제이다.시간 제한: 2초메모리 제한: 128MB 💡알고리즘 설계그래프 정보를 인접 행렬로 저장한다.DFS 구현재귀 함수를 이용한다.방문한 노드를 visited = true(방문 체크)로 설정하고 StringBuilder에 저장한다.해당 노드와 인접한 노드 중 방문하지 않은 노드(visited == false)를 재귀 호출한다.BFS 구현큐를 이용한다.시작 노드를 큐에 넣고 visited = true 로 설정한다.큐가 빌 때까지 다음을 반복한다.큐에서 맨 앞 노드를 꺼내고, StringBuilder에 저장한다.꺼낸 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 넣고 visited = true 로 설정한다. 💡코드i.. 2024. 7. 16.
[백준] 9093번: 단어 뒤집기 💡문제 분석 요약주어진 문장을 단어의 순서는 바꾸지 않고 단어를 모두 뒤집어서 출력하는 문제이다. 💡알고리즘 설계한 문장씩 입력받아 맨 뒤에 “\n”를 추가한다.문장을 한 문자씩 검사한다.문자가 ‘ ‘또는 ‘\n’가 아닌 경우 스택에 추가한다.문자가 ‘ ‘또는 ‘\n’인 경우 스택에 있는 모든 값을 pop(출력)한 다음, ‘ ‘을 추가한다. 💡코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); .. 2024. 7. 16.
반응형