곽로그

문제 www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이1 - 시간초과 - map 의 값을 입력 받을 때, 벽인 경우 그 좌표를 ArrayList에 add한다 - ArrayList를 순회하면서 index에 해당하는 벽의 좌표를 지나갈 수 있는 길(PATH)로 바꾼다 - bfs - index에 해당하는 벽의 좌표를 다시 벽(WALL)로 바꾼다 이렇게 하면 시간복잡도는 NM^2으로 10의 12제곱이 된다. 시간초과가난다 풀이2 시간 초..

문제 programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이 programmers.co.kr 풀이 초 단위로 트럭과 다리의 상태를 써내려가다보면 어떻게 해야할지가 보인다. 초 대기트럭 다리 0 7 4 5 6 _ _ 1 4 5 6 7 _ 현재 다리의 무게+다음트럭의 무게 다리가 버틸 수 있는 무게 - continue 3 5 6 4 _ 다리에 있는 트럭의 위치를 1칸씩 이동한다 현재 다리의 무게+다음트럭의 무게

문제 www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.LinkedList; import java.util.Queue; imp..

문제 www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; c..

문제 www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; class..

문제 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; class Shark{ int x; int y; int size; int eatCount; static int totalEatCount = 0; static int totalMoveCount =0; Shark(int x, int y, int size, int eatCount){ this.x = x; thi..

문제 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 현재 토마토의 위치를 기준으로 북, 동, 남, 서쪽을 차례로 탐색한 후 익지 않은 토마토가 있으면 익은 토마토로 만든다. 북동남서 방향으로 동시에 확산 되는 것이므로 bfs를 통해 탐색을 한다. 처음 입력을 받을 때 값이 1인 좌표를 queue에 add한다. 이 queue가 빌 때까지 bfs로 탐색을 한다. 익지 않은 토마토가 있을 때 map을 업데이트 하는데, 업데이트 하는 값의 의..

문제 www.acmicpc.net/problem/13300 13300번: 방 배정 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 수학여행에 참가하는 학생 수를 나타내는 정수 N(1 ≤ N ≤ 1,000)과 한 방에 배정할 수 있는 최대 인원 수 K(1 < K ≤ 1,000)가 공백으로 분리되어 www.acmicpc.net 풀이 2차원 배열을 활용하면 쉽게 풀 수 있다. 문제 예시에 나와 있는 것 처럼 studentArray[n][m] ( 학년이 n학년이고 성별이 m인 학생의 수)인 2차원 배열을 선언한 뒤 배열을 순회하면서 각 학생수를 K로 나눈 몫과 나머지를 구한다. n학년이고 성별이 m인 학생들이 필요한 방의 갯수는, n학년이고 성별이 m인 총 학생수를 K로 나눈 몫을 구한다. 이때 나머지가 ..