mojo's Blog

문제 링크 => 2146번: 다리 만들기 (acmicpc.net) 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 전형적인 BFS 문제이다. 먼저 대륙별로 숫자를 매기도록 하였다. (1번 대륙, 2번 대륙, ..., i번 대륙) 그리고 각 육지별로 BFS 를 돌려서 바다로 이동이 가능하며 다른 대륙을 발견한 경우 거리를 return 하도록 하여 그 거리들 중에 최솟값이 정답이 된다. 풀이 code #define _CRT_SECURE_NO_WARNINGS #include #include #include #includ..

문제 링크 => 16947번: 서울 지하철 2호선 (acmicpc.net) 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net BFS + DFS 짬뽕 문제이다. 이 문제는 역과 역 사이의 방향이 양방향으로 주어졌고 핵심은 순환이 되는 순환선 즉, 한 역에서 출발해서 계속 가다가 다시 출발한 역으로 돌아올 수 있는 노선을 구분짓는 것이다. 1. 순환선은 DFS 를 활용하여 판별하였다. 판별 방법은 한 역에서 출발해서 계속 가다가 다시 출발한 역으로 돌아올 수 있다는 점을 다음과 같이 해결하..

문제 링크 => 2201번: 이친수 찾기 (acmicpc.net) 2201번: 이친수 찾기 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 들 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 이친수는 다음과 같은 성질을 갖는다고 한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들어서 1, 10, 100, 101, 1000, 1001, 1010, 10000, ... 와 같은 숫자들이 이친수이다. 그렇다면 이 숫자들을 나열하여 규칙성을 찾아보면 다음과 ..

텍스트로 입출력하는 간단한 그래픽 편집기를 만드는 문제이다. 추상 글래스 Shape과 Line, Rect, Circle 클래스 코드를 잘 완성하고 이를 활용하여 4가지 그래픽 편집 기능을 가진 클래스 GraphicEditor을 작성한다. 연결리스트 구현과 비슷한 느낌이여서 직접 코드를 작성해보았다. + 삭제 구현을 할 때, 삭제된 노드의 동적 할당을 해제시키기 위해 System.gc(); 를 호출하였다. code import java.util.*; abstract class Shape{ private Shape next; public Shape() { next=null; } public void setNext(Shape obj) { next = obj; } public Shape getNext() { r..

Bear의 Fish 먹기 게임 만들기 구현 import java.util.*; abstract class GameObject{ protected int distance, x, y; public GameObject(int startX, int startY, int distance) { this.x = startX; this.y = startY; this.distance = distance; } public int getX() { return x; } public int getY() { return y; } public boolean collide(GameObject p) { if(this.x==p.getX() && this.y == p.getY()) return true; else return false;..

문제 링크 => 4256번: 트리 (acmicpc.net) 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 트리를 이용한 분할정복 문제이다. 이 문제는 preorder와 inorder가 주어졌을때 postorder를 구하는 문제인데 약간 까다로웠다. 먼저 예시를 살펴보도록 한다. preorder : 3 6 5 4 8 7 1 2 inorder : 5 6 8 4 3 1 2 7 preorder의 맨 앞부분 3은 트리의 가장 위에 있는 노드이다. 그리고 inorder를 살펴보면 3을 기준으로 5 6 8 4..