공부공간

https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다. W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다. www.acmicpc.net 원숭이는 K번 말처럼 움직일 수 있다. 왼쪽 끝 ( 0,0 ) 에서 시작하여 ( y-1 , x-1 )까지 이동하면서 최단경로를 구하는 문제이다. 최단경로를 구하기위해 BFS알고리즘을 사용했으나.. 방문처리가 상당히 까다로웠다. 먼저, 말처럼이동..

https://www.acmicpc.net/problem/14868 14868번: 문명 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 세계의 크기를 나타내는 정수 N(2 ≤ N ≤ 2,000)과 문명 발상지의 수 K(1 ≤ K ≤ 100,000)가 주어진다. 다음 K줄에는 한 줄에 하나씩 문명 발상지에 해당하는 정사각형의 위치 (x,y)를 나타내는 두 자연수 x와 y가 주어진다. (1 ≤ x,y ≤N) www.acmicpc.net 문명을 bfs로 전파하면서 전체 문명의수가 한개가되는 즉, union-find를 동시에 수행하면서 전체 root가 1개가 되는 시점을 찾으면된다. 편향트리가 될수있기에, rank를 이용하여서 꼭 정리를 해주어야한다. 이러한 disjoint set과 완전탐색이 결합된 문제..

https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있다. ...XXXXXX..XX.XXX ....XXXX.......XX www.acmicpc.net 최적화의 끝.. 문제는 쉽다. MAP에서 . 와 인접한 X는 매초 녹는다. 녹으면서 생기는 .을 통하여 두개의 L이 만날수있는지 물어..

https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4

https://www.acmicpc.net/problem/1325 1325번: 효율적인 해킹 첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다. www.acmicpc.net 신뢰성이 존재하는 컴퓨터 관계에서 하나의 컴퓨터를선택해서 가장많이 해킹할 수 있는 컴퓨터를 뽑는 문제이다. 문제는 단순하지만, N=10000에서 완전탐색을 고민하게되는데, 나도 DFS+DP로 접근하였었다. 바로 틀렸습니다! 가 나오길래 사이클이 있는 경우에서 DP의 값이 이상하게 갱신되는것을 알 수..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동 www.acmicpc.net 예전에 못풀어서 끙끙앓던 문제였는데 다시 생각해보니 쉬웠다. 큐에 들어가는 노드에 벽을 부수었는지? 만 체크하면 된다고 생각했..

https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서 www.acmicpc.net 3차원 BFS를 통해서 S에서 시작하여 E까지 도달하는 문제이다. 한 칸움직이는 사이에 1분이 소요되므로 일반적인 BFS를 돌려주면 된..

악마의 손아귀 스킬을 피해 목적지까지 갈 수 있는지 여부를 체크해주는 문제이다. 덱을 사용하여 처음 입력에 악마의 손아귀를 먼저 처리해주고 이동하는 S는 항상 한개이기 때문에 큐 내에서 같은 시간에 처리된다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWsBQpPqMNMDFARG SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.u..