개발하는 고라니

16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net [BFS] Time Limit Exceeded(TLE)를 높은 확률로 만날 수 있는 문제이다. 여러 가지 방식으로 문제를 풀어봤으나 매번 시간 초과... 결국 AC를 받은 것은 다음과 같은 방법이다. * 갈 수 있는 칸을 저장하는 int[][] move * 빈 공간에 대해 방문 체크 boolean[][] visit * 벽에 대해 방문 체크 boolean[][] wall * 지도 저장 int[][] map 1. 입력을 받으며 벽인 곳의 move..

9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net [BFS + 비트마스킹] 정말 맞왜틀? 이 질문이 여러번 나왔던 문제. 뜻밖의 반례를 찾아서 다행히 AC를 받았다. 1 6 6 .***** .A$B$* ****** .C$D$* ****** **ac** 0 answer : 2 기존 코드는 위의 반례에서 무한루프를 돌았다. 그 이유는 망각해버렸으나 어떤 열쇠를 갖고있는지에 대한 정보 (key)를 전역변수로 두어 BFS내에서 공유하게 했더니 TLE를 피했다. 그리고 "상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 빈 공..

1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net [BFS] 거의 브루트 포스 문제랄까.. 가능한 모든 경우의 수를 다 돌아보는 것 같다. 나는 Set과 문자열을 이용했다. 예를 들어, 1 2 3 5 6 7 8 4 0 이라는 배열이 주어진다면, String str = "123567840"; 이런식으로 문자열로 변환해 Set에 넣어 값이 중복되지 않게 (이미 방문했던 배열을 피하기 위해) 하였다. 결국 Set은 "123456780" 이라는 문자열을 넣게 될 수도, 넣지 않게 될 수도 있는데, 넣지 않게 되는 경우 '-1'을 출력하면 된다. 코딩 기술이 부족하다보니, 잡기술을 여러가지 사용한..

14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 모든 정점에 대하여 다른 정점으로의 최단 경로를 구하는 문제이므로 n * Djikstra / Floyd Warshall을 사용할 수 있겠다. [Dijkstra] # Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static class Edge implements Compa..

1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net [BFS * m회 + Kruskal (=Union-Find, Sort)] 어느정도 발상의 전환이 필요한 문제라고 생각된다. 'S'에서부터 'K'를 찾아가는 것이 아닌 각각의 'K'에서 또다른 'K'나 'S'를 찾아가는 방법으로 풀어보았다. 그러므로 m개의 'K'가 주어지면, 각각의 'K'의 위치에서 BFS를 수행하며 다른 'K'나 'S'를 만날 때 간선의 정보를 만들어 List에 담아주었다. 이 때 크루스칼 알고리즘을 수행하려면 출..

[Floyd-Warshall] 조금 독특한(?) 문제라고 생각된다. 매번 모든 정점에 대해 다른 정점들로의 최단 거리를 구하는 것을 목표로 풀었는데 이번엔 모든 최단 거리를 주어지고, 초기 인접 행렬을 구해보라고 하는 문제라서 일까. 문제를 풀기 위해 boolean origin[ ][ ]이라는 배열을 준비했다. 이 배열의 원소 값이 true가 된다면, 기존에 있던 간선이 아닌 다른 정점을 통해 이어진 간선이라는 것을 나타내게 될 것이다. 만일 현재 3번 정점에 있다고 하고, 5번 정점으로의 최단 거리가 a일 때, map[3][5] = a 이다. 그리고 1번 정점을 거쳐서 5번 정점으로 가는 거리를 map[1][5] = b이고, 정점 3에서 정점 1로의 거리 map[3][1] = c라고 할 때 a == b..

1486번: 등산 첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000 www.acmicpc.net [Dijkstra / Floyd Warshall] 모든 정점에서 다른 모든 정점에 대한 최단 경로를 구하는 문제이므로 다익스트라를 이용하거나, 플로이드 와샬을 이용해도 무방할 듯 하다. 나는 N x M개의 모든 정점에 대해 다익스트라 알고리즘을 수행하였다. 우선 map이 알파벳으로 주어지는데, 각 알파벳은 그에 맞는 높이를 정수형으로 가진다. 따라서 map을 저장할 때 char가 아닌 int로 변환해서 저장하였다. for(int i=1; i

10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net [Floyd Warshall (플로이드 와샬)] 일반적인 플로이드 와샬 알고리즘으로 모든 정점에서 다른 모든 정점으로의 최단 거리를 구한다. 이 때 가볍고 무겁다는 것은 양방향이 아닌 단방향이다. 그러므로 a정점에서 b정점에 대하여 어느 것이 가볍고 무거운지 모르고, 마찬가지로 b정점에서 a정점에 대하여 어느 것이 가볍고 무거운지 모른다면 (distance[a][b] == INF && distance[b][a] == INF) 비교 결과를 ..