CodingTest

아아앗악아아악 발표에 걸렸다. 자세히 정리해보도록 하자,, 문제 이해1. 사용자 A와 B가 있다. 두 사용자는 동시에 움직인다.2. 매초마다 이동 한다. 만약 이동한 좌표의 위치가 BC에 들어오면 접속이 가능하다.3. 이렇게 BC에 들어올 때마다 충전량을 합한 최대값을 찾아야한다.첫 번째 시도사용자가 두 명밖에 없어서 사용자가 m만큼 움직일 때마다 저장되는 충전량을 더하려고 했다.그래서 이차원 배열 map을 만들어서 BC의 성능을 저장하려고 했다.맨해튼 거리를 이용해서 충전 범위에 들어오는 map의 좌표값에 P(성능)을 저장하는 것이다.c >= Math.abs(x-i) + Math.abs(y-j)    두 번째 시도근데 생각을 해보니 BC가 겹칠 수가 있었다. 그래서 이차원 배열을 이용하는 게 아니라는 ..

#17826 공주님을 구해라문제로가기문제이해용사에서 공주까지 갈 때 최단 거리를 구해야한다.용사은 상하좌우 이동할 수 있다.벽은 이동할 수 없다. 빈칸만 이동할 수 있다.1칸당 이동하는데 1시간이 소요된다. T 시간이 넘어가면 fail을 출력해야 한다.* 조건 * 그람 위치에서 그람을 만나면 벽도 이동이 가능한다.   해결 방법 고안1. 최단거리 임으로 bfs를 이용한다.2. 검의 위치에 도달하면 que를 사용하지 않고 바로 그 거리에서 공주까지의 직선 거리를 구한다. 약간의 삽질처음에 검이 위치까지 가기전에 거리를 구했고, 검의 위치에서 다시 que를 사용해서 최단거리를 구하려고 했다.그럴 필요 없이 그냥 검의 위치에서 직선방향으로 (x , y)에서 공주의 위치 ( n-1, m-1)를 구하면 됐었다. ..

#18428 감시피하기문제로가기문제이해장애물, 선생님, 학생이 있고 장애물이 학생이 있는 row나 column에 있게 되면 선생님은 학생을 발견하지 못한다.선생님이 상하좌우에서 학생을 발견한다면 no를, 발견하지 못한다면 yes를 출력단 장애물은 3개까지 설치할 수 있다.해결방법 고안장애물을 설치하는 건 - dfs선생님이 상하좌우에서 학생이 있는지 탐지하는 건 - bfs로 생각했다. 지금 생각해보면 bfs는 필요없는 듯 하긴 하다.dfs로 장애물 3개를 추가한 map을 만든다 -> 그 map에서 바로 check 함수로 bfs를 호출한다.check 함수에는 일단 선생님의 위치를 que에 넣어두고 그 위치에서 열과 행을 다 검사해서 학생을 발견하면 false를 하고, 장애물을 발견하면 반복문을 break하고..

#8275 햄스터문제로가기 문제 이해,  해결 방법 고안    이 문제는 중복 순열 (순서가 있어야 하고, 숫자가 중복으로 들어갈 수 있음)이다.중복 순열 중에서 m에 맞는 조건들을 다 만족하는 것을 출력하는 구현 문제이기도 하다. 처음 푸는데 1시간 이상 걸렸고, 한번 더 풀어보는데도 30분 이상은 걸렸다. 마지막에 출력에 신경 써야 TestCase를 다 만족시킬 수 있다.어차피 순열로 나오는 배열들은 오름차순으로 나오기 때문에 이 조건은 신경쓰지 않아도 됐었다!그리고 나는 마지막에 최종 나오는 (출력해야 하는) 후보를 res 배열에 담았는데 n이 1이 될 수 있기도 때문에 초기화를 null로 해주는 것도 처리해줘야 한다 ~! 애증의 햄스터 코드는 아래에 있다.더보기import java.io.*;imp..

#14502 연구소문제이해0, 1, 2 숫자가 있고 벽(1)을 3개 추가로 세워서 바이러스(2)가 퍼지는 수를 막아서 최대한 빈칸(0)의 개수가 큰 걸 찾아야 한다.   해결 방법 고안- 벽을 3개 세우고 -> 바이러스 퍼지고 -> 0개수 세기- 위에 로직을 계속 반복해야 하는 구조이다.- 그래서 벽을 세우는 건 dfs, 바이러스 퍼지는건 bfs, 개수 세는 함수 이렇게 총 3개의 함수를 만들기로 하였다.- 최종으로 최대한 큰 max_value를 찾아서 결과를 출력해주면 끝이다.코드설명아래 코드에 주석으로 달아놓았다.import java.io.*;import java.util.*;public class Main { private static BufferedReader input = new Buffe..

네,, 저 자바로 코테 언어 변경 했슴니다 ,,매주 3문제씩 문제 풀고 블로그에 업로드 하기로도 했슴니다,, #2589 보물섬문제 이해0. 육지와 육지에서 가장 멀리 떨어진 거리에서 움직이는 시간을 구해야 한다.1. 1칸당 1초이고 방문했던 곳을 방문해서는 안된다.2. 가장 멀리 떨어진 점이고 그 점에서는 최단거리여야 한다.  해결 방법 고안1. 최단 경로를 구해야 하므로 BFS를 사용하기로 생각했다.2. 두 점이 나와있지 않기에 한 점 (육지)를 잡아서 그 점에서 부터 멀리 떨어진 것을 BFS로 return 해준다.3. 그 점 들 중에서 가장 멀리 떨어진 것을 구해야 하므로 Math.max을 사용했다.4. 즉, 육지인 한점 -> bfs 사용해서 가장 최단 거리이면서 가장 멀리 떨어진 시간 return5..

문제 정답 bfs로 구현해야겠다. 그리고 구현은 했지만, 총 인구 이동을 구해야 했다. 그래서 인구 이동을 하고 난 후의 변한 상황을 다시 graph에 반영하고 반복문을 돌려야 했는데, 그게 잘 구현이 안됐다 먼저 인구이동 되는 x,y좌표를 넣어주기 위해서 united라는 배열을 생성했다 그리고 bfs에서 return값으로 넣주었다. 결국 while 문으로 연합된 나라가 있는 경우 flag=1로 설정해서 답을 구해준다. county라고 받고 county가 있는 경우 값을 바꾸어준다 의외로 구현은 납득 가능한 수준의 문제였다:( #bfs로 상하좌우 다 파악을 해서 count를 해준다 #sum도 구한다 #방문하지 않거나 연합인 국가가 아니면 반복해서 파악한다 from collections import deq..

문제 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. 예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 ..