웹개발 성장기

2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 태그는 다익스트라이지만 우선순위큐로도 풀 수 있다. (사실 우선순위큐로 풀었는데 질문글 보니 다익스트라 코드도 있어서 다익스트라로도 풀어봄...ㅎㅎ) 우선순위큐 풀이 좌표 정보 + 검은 방을 흰 방으로 바꾼 횟수를 class로 선언한 후 검은 방을 흰 방으로 바꾼 횟수가 작은 순으로 큐에서 뽑으면 된다. visited 배열로 방문 유무를 확인하며 다음 좌표가 검은방이면 cnt + 1, 흰 방이면 cnt값을 큐에 넣는다. 적은 횟수부터 탐색하기 때문에 끝방 좌표에..

1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 풀이 반례가 엄청 많이 존재하니 혹시라도 틀렸다면 질문게시판의 반례모음집 게시글을 참조하며 고쳐나가면 좋다. 어떻게 풀지 생각하다 BFS N부터 시작해서 100까지 가는 방법을 찾았다. 문제 분류는 브루트포스로 되어있는데 말 그대로 브루트포스로 0부터 1000000까지 모든 경우를 계산하는 방법도 있다. N에서 출발하는데 현재 숫자가 누를 수 있는 번호이면 (isPossibleToPress(int n)으로 각 자릿수에 누를 수 없는 수가 있는지 ..

9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 BFS로 네 가지 경우 (DSLR)를 전부 탐색한다. int, String을 저장하는 custom class DSLR을 구현했다. 큐에는 (현재 숫자, 지금까지 부른 명령어)를 저장한다. 탐색하다가 현재 숫자가 B가 되면 지금까지의 명령어를 출력한다. visited[]로 숫자 중복 여부를 확인한다. D, S, L, R을 method로 만들어서 사용했다. 코드 import java.io.*; import java.util.*; public cla..

19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 시간초과가 났던 문제. 검색하여 찾아보니 연료를 무한으로 충전할 수 있어서 그렇다고 한다. 문제에는 적혀있지 않은 예외사항이 두 가지 있다. 택시 기사가 승객의 위치까지 도달할 수 없는 경우 (거리 = INF) 승객을 도착지까지 태울 수 없는 경우 (거리 = INF) 되는지 안되는지 판단할 때 단순히 거리와 연료량 여부로 판단하면 안되고 이 부분도 고려해야 문제가 통과한다. 구현문제라 문제에 충실하면 생각보다 어렵지 않..

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[]을 두는데, 여기선 해당 위..

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

16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 풀이 혼자 일부러 더럽고 어렵게 푼 느낌? 🙄 암튼 오래걸림 문제에 나온 그대로 시뮬레이션 문제 풀듯 풀었다. 짜잘짜잘한 조건들이 많아서 테케 넣어보고 수정하고 하다보니 푸는데 오래걸렸다.. 고민거리와 삽질의 흔적들 두 동전은 어떻게 동시에 움직이지? 일차원 배열을 생성해서 반복문으로 변수 값을 할당했다. 0

BFS지만 동시성을 생각해야 하는 문제 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 물과 고슴도치 각각 방문체크를 할 큐를 두고 물 → 고슴도치순으로 BFS탐색을 했다. Logic 데이터를 입력 받을때 고슴도치의 시작 위치를 hedgehog큐에 넣고 해당 map의 위치는 S에서 .으로 마킹한다. 물의 위치를 입력받을 경우 water 큐에 넣고 visited = true로 놓는다. BFS 탐색을 시작한다. while문은 더이상 고슴도치 무빙이 불가능할 때 까지 반복된다. 물부터 영역을 넓힌다. 큐 크기가 유동적이기..