www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 중간 중간에 조건들을 처리해줘야 할 것이 많다. 디버깅이 안되서 아예 다시 풀었다. 도착지, 출발지 정보를 다 저장하고 taxi클래스를 또 따로 만들어줬다. 한 사람의 도착지 = 다음 승객의 출발지이거나 초기 택시 출발지 = 이미 승객이 거기 서있음 의 경우로 택시 위치의 승객은 또 따로 처리해줘야 된다. 각 승객은 (출발지 != 도착지) 정보를 가졌지만 모든 승객이 같은..
www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net subset으로 집합을 나눈다. vis[번호]=true => a집합, false면 b집합 만약 리스트 두 개를 만들어서 각각 집어넣는다. 리스트 하나라도 길이가 0이다 => 나머지 몰빵 => 집합 2개가 안됨 => return 리스트 두 개의 길이를 합쳤는데 n이 안됨 => 집합이 3개 이상이라는 뜻 => return 그 다음에는 한 집합 내에서 bfs로 인접리스트를 돌리며 한 집합의 모든 원소가 연결되는 지 확인한 후 두 집합 합..
www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 청소년 상어를 풀고나서 이 문제를 푸니 dfs가 익숙해서 dfs로 경우를 탐색하다가 메모리 초과가 났다. 가끔 bfs로만 되거나 dfs만 되는 문제들이 있어서 헷갈리는데 최단 시간 (같은 위치 구간에서 동시에 탐색할 때)는 bfs이고 모든 경우의 수를 다 돌아봐야하는 경우 (청소년 상어처럼 먹는 물고기 번호가 가장 큰것을 구하는 것)은 dfs인 것 같다. 물이 차오를 지역도 못간다는 것은 즉, 물이 찬 것과 같다라는 뜻이라..
www.acmicpc.net/problem/17276 17276번: 배열 돌리기 각 테스트 케이스에 대해 회전 연산을 마친 후 배열의 상태를 출력한다. n줄에 걸쳐 각 줄에 n개의 정수를 공백으로 구분하여 출력한다. www.acmicpc.net 대각선 45도, -45도로 배열을 돌리는 문제. 주 대각선들 외에는 그대로 냅둔다. import java.util.Scanner; public class Main { static int n,t,d; public static void main(String[] args) { Scanner sc=new Scanner(System.in); t=sc.nextInt(); for (int tc = 1; tc
www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 물고기 이동은 구현에서 상어이동은 dfs로 완탐을 돌려줘야되는 문제여서 복잡했다 ㅠㅠ 지쳐.. 중간에 상어가 멈춰서 ?? 했는데 나는 상어이동을 bfs로 구현했고 물고기가 있는 칸으로만 이동하는 것으로 짰더니 빈 칸으로는 이동을 못해 오도가도 못한 상태로 끝나버렸다. 추후 빈 칸도 갈 수 있도록 했더니 통과되었다. 칸이 4x4로 정해져있기 때문에 무조건 3번 이동이 가능한지 for문으로 확인하..
www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 다른 것은 일반 bfs문제와 크게 다를 것이 없는데 배열 회전하는 부분이 어려웠다 ㅠㅠ 예전에 한 번 해봐서 괜찮겠지 했는데 수학 계산을 못하겠어서ㅋㅋㅋㅋㅋ 길이가 4일때 첫 열의 세로줄 2 1 5 7 을 첫 행의 가로줄로 만들기 위해서 2 1 5 7 가로줄의 열 번호와 행번호를 sx, sy라는 변수를 따로 만들어서 증가시키고 첫 열의 세로줄은 for문의 변수를 돌리는 방식으로 해줬다. 내일..
www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net arraylist는 검사 시작점과 연합국인 곳들의 좌표가 들어가는 리스트이다. 1. 방문 안된 곳에서 상하좌우를 검사하면서 경계를 열 수있는 곳을 검사한다. 연합국이 되면 sum+=연합국 인구수, cnt(연합국에 들어가는 개수)+1해주고 arraylist에 새로운 연합국의 좌표를 넣어준다. 2. 시작한 곳에서 bfs로 최대한 검사할 수 있는 곳까지 다 검사가 끝나면 arraylist 좌표에 해당하..
www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net import java.util.ArrayList; import java.util.Scanner; public class Main { static int n,k; static int[] belt; static ArrayList list=new ArrayList(); static boolean[] pos; public static void main(String[] args) { Scanner ..
www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net bfs로 뭐든 되는구나 싶었다 1번이랑 n번이 연결된다는게 뭔가 싶었는데 범위를 넘어가면 그만큼 빼서 다시 안의 범위로 들어오게 해야된다 그 다음에는 파이어 볼 개수만큼 큐에 집어넣고 그 길이만큼만 bfs로 돌린 후 다시 새로 만든 파이어볼을 큐에 넣고 k번 돌리면 된다. import java.util.ArrayList; import java.util.LinkedList;..
www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 앞뒤를 나타내는 좌표 이동을 추가해서 추가로 검사해준다. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int h,y,x; public Pos(int h, int y, int x) { super(); this.h = h; this.y = y; this.x = x; } } pu..