개발하는 고라니

정수형 1차원 배열 arr을 인자로 받아 정수형 1차원 배열을 반환하는 메서드 shuffle이다. 이 메서드는 인자로 받은 배열을 무작위로 섞어준다. 보통 셔플을 하면 원소가 중복되지 않게하기 위해 부가적인 처리가 필요한 경우가 있다. 하지만 이같은 경우는 배열의 원소를 직접 다루는 것이 아닌, 배열의 인덱스를 사용해 Swap을 하므로 값의 중복이 일어날 일이 발생하지 않는다. static Integer[] shuffle(Integer[] arr) { Random ran = new Random(); Integer[] result = arr; for(int i=0; i

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를 피했다. 그리고 "상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 빈 공..

상속이라는 단어는 아마 대부분 알 것이라고 생각된다. Java에서의 상속은 무엇일까? 자식 클래스가 상속받고 싶은 부모 클래스를 선택해서 물려받는다. 이때 상속받는 클래스 = 자식/하위/서브 클래스, 상속을 해주는 클래스 = 부모/상위/슈퍼 클래스 라고 한다. Java에서는 'extends' 키워드를 사용해 상속을 선언한다. 자식 클래스가 상속을 하게되면 부모 클래스의 필드와 메서드를 물려받는다(능력 및 기능을 제공받는다). 하지만 부모 클래스 멤버의 접근 제어자가 'private', 'default'라면 상속은 받을 수 있지만 접근은 어렵다. 그리고 자식 클래스가 여러 부모로부터 다중 상속받는 것은 불가(단일 상속)하다. 반대로 부모 클래스는 여러 자식 클래스에게 상속을 해주는 것이 가능하다. Has ..

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