곽로그

문제 www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 풀이 반복의 기본단위를 생각해보면 아래와 같다 현재위치에서 다음위치로 이동 → 다음위치에 있는 모래 뿌리기 → 이동한 위치를 현재위치로 업데이트 그럼이제 여기서 위의 반복을 언제까지 반복하는지를 생각해보면 "현재위치에서 다음위치로 이동" 했을 때 이동한 위치가 맵영역을 벗어나면 반복을 멈추고 나간모래의 총량을 return 하면 된다. 여기까지의 기본구조는 아래와 같다 sta..

문제 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 첫번째 풀이 (문제조건을 고려하지 않은 풀이) 문제 접근 ​ 전체 로직은 아래와 같다 1. x,y,d1,d2의 모든 경우의 수를 구한다 2. 경우의 수에 대해서 구역5를 그린다 3. 구역5를 그릴 수 없는 경우 다른 경우로 넘어간다 4. 구역 5를 그릴 수 있는 경우 1,2,3,4,5구역의 인구수를 구한다 ​ 문제에서 변하는 값은 x,y,d1,d2이고 이 값의 변동 범위는 1~N이다. 따라서 모든 경우를 다 따질 수 있다고 생각했는데, 그 이유는 (x,y)정하기 ..

문제 www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이1(시간초과) node를 순회하면서 각 노드에 대해 처음 탐색을시작하는 노드와 탐색이 종료되는 노드가 같으면 팀을 이루고, 다르면 팀이 아니다. 위의 표를 예로 들어보자. node 1에 대해서 탐색을 시작한다. 그러면 차례대로 1->3->3 을 방문하게 되는데, 3의 다음노드는 3이고, 이는 이미 방문했던 노드이므로 1->3 ->3에서 탐색을 종료한다. 이때 탐색시작노드 1과 탐색 마지막 노드 3이 다르므로..

문제 www.acmicpc.net/problem/3055 풀이 1초마다 물과 고슴도치가 이동하는 것을 그림으로 나타내면 아래와 같다 물과 고슴도치가 이동할 수 있는 조건이 다르므로 (물은 동굴을 지나갈 수 없고, 고슴도치는 동굴을 지나갈 수 있다) 물이 이동하는 위치를 넣는 큐하나와 고슴도치가 이동하는 큐하나, 총 2개의 큐를 이용해 bfs를 진행하면 된다. 그런데 이때 while(queueWater.isEmpty)를 조건으로 탐색을 하면, 1초에 해당하는 물만 이동하는게 아닌게 된다. 따라서 second라고 하는 변수를 하나 선언해서 second 값에 해당하는 거리를 이동한 물, 고슴도치만 이동하게한다. 코드 import java.io.BufferedReader; import java.io.Buffer..

문제 www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 참고한 블로그 bcp0109.tistory.com/entry/%EB%B0%B1%EC%A4%80-9466%EB%B2%88-%ED%85%80-%ED%94%84%EB%A1%9C%EC%A0%9D%ED%8A%B8-Java 백준 9466번. 텀 프로젝트 (Java) 문제 링크 : https://www.acmicpc.net/problem/9466 싸이클을 형성하지 못하는 노드 갯수를 찾는 문제입니다. 일반적인 DFS로 모든..

문제 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 시간 초..

문제 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..