https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net ✏️ 문제 🔐 문제 해결 예를들어 아래와 같은 5X5 배열이 있다고 해보자 0 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 1 1 0 0 0 1 0 그림으로 표시하면 아래와 같을 것이다. 화살표 방향과 같이 시작점(0,0) 에서는 두 가지 방향으로 갈 수 있을 것이다. 하지만 1번으로 벽을 뚫고 간다면, 아래의 문제점에 부딪히게 된다. 도착지점으로 가기 위..
https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 이 문제는 이전의 풀었던 7576번 토마토와 비슷한 문제이다. 이 문제에서의 다른 점은 토마토가 2차원 배열에 담기는게 아니라, 3차원 배열에 담기기 때문에 상,하,좌,우,앞,뒤까지 총 6번을 체크해줘야한다. ✏️ 문제 🔐 문제 해결 어려울 것이 없다. 이전과 동일한 방식으로 처리할 것이고, 그저 체크해야 할 곳이 2곳이 늘었다는 점 외에는 말이다. 토마토를 담기 위한 3차..
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net ✏️ 문제 🔐 문제 해결 이 문제는 미로 탐색 문제처럼 풀면 된다. 대신 이 문제에서 주의해야할 점은 미로 탐색 문제처럼 한곳에서 출발하는게 아니라, 시작점이 여러지점이라는 점이다. 이것 때문에 머리 아팠는데 생각해보면 그리 어렵지 않다. 아래 코드를 보면서 살펴보자. int[][] days = new int[N][M]; int[][] tomatos = new int[N][M]; ..
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net ✏️ 문제 🔐 문제 해결 이 문제는 이전의 풀었던, 그림 문제처럼 풀면 안된다. 이전 문제처럼 풀게 되면 최단거리를 구하지 못한다. 그래서 이 문제는 시작지점(0,0)으로 부터의 모든 칸의 거리를 계산하여 또 다른 배열에 저장을 할 것이다. 이게 무슨 말이냐면, 아래 그림을 보면 우리가 구해야 하는 경로는 빨간색 경로인데, 어떻게 구하냐면 위에서 말했듯이 시작점으로부터의 거리를 계산한 배열을 생성해줄것이다. int[][] dis..
https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net BFS의 개념을 가장 잘 이해할 수 있는 문제라고 할 수 있다. 차근차근 한번 풀어보도록 하자. ✏️ 문제 🔐 문제 해결 값이 1이면 색칠이 된 부분이니까, 모든 그림을 전부 돌면서 1이거나 방문하지 않은 그림을 체크하면서 처리해주면 될 것 같다. 우선 모든 그림을 2차원 배열에 담아주도록 한다. (StringTokenizer를 이용해서 각각 원소를 넣어준다.) arr = new int[n][m]; /..
https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 이제부터 열심히 알고리즘 문제를 풀어보아야겠다.. 하하 정말 간단한 문제인데, 시간 초과가 자꾸 떠가지고 삽질했다.. 그냥 배열에 넣고 하나하나 비교했는데 -> 시간 초과 위 방법 + 배열 정렬 후 비교 -> 시간 초과 데이터들을 반으로 나눠서 비교하면 시간이 절반으로 줄을 것으로 예상!! 핵심 코드 for (int i = 0; i < M; i++)..
