개발하는 고라니

11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net [BFS] main에서 하는 일은 단 4가지다. 1) visit 초기화 2) 맵 BFS로 스캔 하며 터트릴 것이 있다면 터트리고, flag = true로 설정(flag == false면 종료 시퀀스) 3) score++ 4) 블록들을 아래로 내려주는 down() 다시 1~4 반복. 2) 에서 Queue를 이용해 BFS를 구현하였고, 큐에 들어가는 좌표를 List에 담아 만약 4개 이상 담겼다면 터트리고 마지막에 List를 초기화시켰다. #..

1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net [Union-Find] 입력은 인접 행렬 형태로 주어지지만, 크루스칼 알고리즘을 사용할 때 처럼 모든 간선의 정보를 하나의 리스트에 담았고, 이 리스트를 가지고 유니온 파인드를 하여 서로 연결된 그래프라면 연결시켰다. 그리고 입력으로 주어진 m개의 여행 도시 배열의 각 원소의 부모가 첫 번째 원소의 부모와 다르다면 이 여행 순서는 이루어질 수 없으므로 "NO"를 출력한다. # Code public class Main { static class Edge{ int ..

17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net [DFS + 동적 프로그래밍] 가로 세로 대각선 그림처럼 다음 파이프를 놓는 것은 현재 파이프가 어떻게 놓여져 있는지에 의존한다. 그래서 dp[n][n][3]이라는 배열을 사용했고, dp[n][n][0]은 가로로 놓여져 있을 때, dp[n][n][1]은 대각선, dp[n][n][2]는 세로로 놓여져 있을 때의 경우의 수를 나타낸다. 그리고 대각선의 경우 대각선을 나타내는 좌표 뿐 아니라, 좌측, 상측 모두 빈공간이어야 함을 명심해야한다. ..

2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net [BFS] 크루스칼을 이용한 '다리 만들기 2'와 비슷한 문제. [백준] 17472번 : 다리 만들기 2 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바 dev-gorany.tistory.com 먼저 입력받은 지도를 Labeling(BFS)을 통해 연결된 섬 별로 나누어준다. 섬은 2개 이상 나오게 된다...

2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net [BFS] 개인적으로 브루트 포스 방법을 좋아하지 않는다. 문제에서 정점은 최대 50x50 = 2500개라서 브루트 포스를 해도 시간이나 메모리적으로 촉박하진 않지만, 다른 방법으로 풀어보고 싶었다. 그래서 주어진 map에서 'L'이면 주변의 'L'이 몇 개인지 세어 우선순위 큐에 좌표(i, j)를 넣었고, 주변에 'L'이 가장 적은 좌표부터 꺼내어 BFS를 하며 거리를 측정하였다. 그러나 이 방법에는 치명적인 오류가 있었다. W L W L W L L L L L L..

5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net [DFS] 이런 DFS문제를 전에 풀어본 것 같다. 철수와 영희가 각각 i, j에 있을 때 철수가 왼쪽(-1), 오른쪽(+1)로만 움직일 수 있을 때 몇 번만에 영희를 만날 수 있는가? 와 같은 문제. 다만 처음에 오답을 받았다. 아무래도 DFS는 최단 거리를 찾기엔 부적합한 면이 없지않아 있으니 말이다. 다시 말해, 특정한 정점에 처음 도착했는데, 그 때가 최소값이 아닐 수 있다는 말이다. 그래서 대부분 BFS로 풀으신 것 같다. 하지만 DFS로도 264ms를 받고 AC했..

13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net [DFS] 0번부터 N-1번을 시작 정점으로 총 N번의 DFS를 실시하는데, 각 DFS가 끝나면 해당 정점의 visit[current] = false로 다시 변경한다. 이는 백트래킹 문제에서 주로 쓰던 방법이다. 해당 아이디어의 출처는 다음 링크에 있다. www.acmicpc.net/board/view/34026 그리고 DFS를 한층 한층 진행할 때마다 depth를 증가시키며, depth가 5가 되면 결과 flag를 true로 변경하고 루프의 진행을 멈춘다. # Code public class Main { static List[] list = new ArrayList[..

9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net [Dijkstra * 3] 발상의 전환이 필요한 문제라고 생각된다. 문제에서 죄수 2명이 등장하여 이 2명이 여는 문의 개수를 세려고 하니, 잡아야 할 문제점이 잡히지 않았다. 그래서 여러 사람들이 사용한 제 3의 인물을 등장시켜 3명이 문을 여는 것으로 문제를 풀었다. 죄수 2명은 감옥 안에 주어지고, 제 3의 인물 상근이는 (0, 0)에서 시작한다. 이 3명은 모두 다익스트라 (BFS로 해도 무관하다고 생각됨)를 이용해 모든 문을 열고, 각 지점마다 몇 개의 문을 열고 ..