웹개발 성장기

1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 다양한 방법이 있는 것 같지만 다익스트라로 풀었다. 우선 여행 계획에 있는 도시들은 중복될 수 있으므로 순서를 배열로 입력받음과 동시에 HashSet으로 받았다. HashSet에 있는 도시들만 다익스트라 알고리즘으로 경로를 갱신했다. 만약 위치가 INF로 남아있으면 그 도시로는 방문이 불가능하다는 의미이다. 마지막으로 여행 계획에 있는 도시들을 for문으로 순회하면서 INF가 나오면 바로 "NO"를, 그렇지 않으면 "YES"를 출력하게 했다. 코드 impo..

1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 풀이 일단 이 문제는 다익스트라가 맞다. 틀려서 결국 구글링을 하긴 했는데 대부분 이분탐색과 BFS를 조합하여 했지만 이분탐색으로 풀면 뭔가 문제의 취지에 안맞는 느낌(?)이 들어서 다익스트라 코드도 찾아봤다. 다익스트라로 풀 경우 우선순위큐를 사용하여 중량 기준 내림차순으로 들어가도록 한다. 일반적인 최단경로 찾기의 경우 시작노드 기준 거리 정보를 업데이트를 하는 dist[]을 두는데, 여기선 해당 위..

15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 풀이 사다리를 코드로 어떻게 표현해야 할지 고민을 엄청 한 문제!! method를 기능별로 만들어서 풀었더니 군더더기 없이 한번에 통과! 이차원 배열을 만들고 한 column을 한 세로선이라고 두었다. 그리고 가로선은 인덱스 값을 줘서 표시했다. 이렇게 한 이유는 만약 1로만 표시하면 내려갈 때 양 옆에 가로선이 존재하면 이게 옆동네 가로선인지 내 가로선인지 알 길이 없다. 따라서 내 가로선인지 바로 구분하기 위해 인덱스를 두었다. 가로선은 3개가 넘어가면 -1..

11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 풀이 완전 시뮬레이션 문제 = method를 많이 만들어야 함 처음에 뿌요 위치를 큐에 가져온다. (getPuyo()로 구현) 이제 뿌요 있는곳만 터트릴 수 있는지 확인 터트릴 수 있는 얘들 싹 모아서 비우고 맵 정리 한 연쇄가 끝나면 정답 카운트++ 풀기 전 의문점 위에서부터 터짐? 아래서부터 터짐? 동시에 두 개 이상 터지면 어떻게 됨? 동시에 터져야 한다. 여러번 터져도 연쇄는 한 번만 친다. 터지는 뿌요를 찾았다. 이제 이걸 어떻게..

1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 우선순위큐를 이용한 다익스트라를 3번 실행한 후 경로가 존재하면 최단경로 출력, 없으면 -1을 출력하면 된다. 출발점, 도착점, 거치는 두 정점을 각각 A, B, X, Y라고 하면 A -> X, Y X -> Y, B Y -> X, B 이렇게 각 정점에서의 최단경로를 구한다. 최단경로는 dist[3][N + 1] 이렇게 이차원 배열을 만들어서 저장했다. A -> X -> Y -> B, A -> Y -> X -> B..

16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 풀이 배열로 수를 저장하고 선택한 수에 대해선 visited = false로 처리하여 백트래킹으로 진행한다. 시행착오 처음에 백트래킹 수행하는 method의 인자를 고른 수로 했다. 이렇게 되면 left, right가 linear하게 선택되서 답이 제대로 안나왔다. for문 안에 넣어야 하는데 어떻게 바꿀지 모르겠어서 결국 솔루션을 참고했다. method의 인자는 n과 m 문제처럼 depth를 인자로 넣고, depth가 N-2가 되었을 때 max값인지 아닌지..

3019번: 테트리스 테트리스는 C열 필드위에서 플레이하는 유명한 게임이다. 필드의 행의 수는 무한하다. 한 번 움직일 때, 아래와 같은 일곱가지 블록 중 하나를 필드에 떨어뜨릴 수 있다. 블록을 떨어뜨리기 전에 www.acmicpc.net 풀이 문제 그대로 정직하게 구현하면 되는 문제! 블록 모양을 어떻게 판단할지가 가장 큰 고민이었다. 배열? 리스트? 그림 그려서 수동으로 해보니 바닥면 높낮이를 체크하면 됨을 알 수 있었다. 각 테트리스 블록별로 회전했을때 나올 수 있는 가능한 모양을 모두 저장할 수 있는 ArrayList 을 만들고, 처음 입력받은 모양 번호로 초기화되게 했다. (getBlockShape()) 블록 모양에 따라 올라와야 하는 바닥면의 높이를 저장했다. 그리고 바닥면에 대해 블록을 끝..

1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착 www.acmicpc.net 풀이 이해가 안됐는데 이 블로그를 참고하여 겨우 이해할 수 있었다... 벨만-포드를 이렇게도 풀 수 있구나 했던 문제 특이하게 negative cycle이 아닌 positive cycle을 찾는 문제이다. 일반적인 벨만-포드는 N-1까지 최단 경로를 갱신한 후 마지막으로 한번 더 돌아다니면서 사이클 여부를 판정한다. 하지만 이 문제에선 사이클이 있는지 검사 뿐만 아니라 시작 지점부터 도착 지점까지의 경로가 있는지도 알아야 한다. 따라서 충분한 edge rela..