코딩브론즈

https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 0) 변수 설정 N : map의 크기 fuel : 연료 map : 지도 (N by N) tr, tc : 택시의 위치 distanceMap[r][c] : 현재 택시 위치에서 (r,c) 까지의 거리. 못 가는 경우가 있으므로 -1로 초기화 한다. isVisited[r][c] : (r,c) 위치를 방문했는지 체크 1) 입력값을 담을 Passenger 클래스를..

https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 1) bfs로 승객을 찾는다. 이때 PrioritiQueue를 써서 우선순위가 높은 순서대로 뽑아야 한다. 2) 승객을 찾을때 생긴 비용을 총 연료에서 뺀다. 이때 연료가 바닥나면 실패. 3) 승객을 찾고도 연료가 바닥나지 않으면 해당 승객의 번호에 맞는 도착지를 찾는다. 4) 도착지를 찾을때 생긴 비용을 총 연료에서 뺀다. 이때 연료가 0 이하면 실패..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 풀이 1) 로봇 청소기의 위치와 방향을 저장할 클래스 Node 를 생성. 청소의 유무를 저장할 boolean형 배열 isCleaned[][] 선언, 입력된 영역을 표시할 map[][] 배열 선언. 2) BFS 방식으로 이동할 영역을 탐색한다. 2-1) 현재 위치한 좌표가 청소 되지 않은 경우 isCleaned 를 true 로 바꾸고 횟수 1 추가. 2-2) 방향 전환 규칙을 찾고 공식을 만들고 ..

www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 1) 방문체크할 visited[] 배열을 만듬. 사이즈는 200001. N이 최대 10만이고 * 2 하면 20만이 나올 수 있으므로. 2) bfs를 돈다 class의 멤버는 cnt 2-1) X = 2 * X : cnt = cnt 2-2) X = X - 1 : cnt = cnt + 1 2-3) X = X + 1 : cnt = cnt + 1 3) X = K 가 되면 끝 4) ..

www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 풀이 1) 단순한 경로 => 방문한 곳 재방문 x => isVisited[][] 배열만 잘 쓰면 장땡 2) N은 14보다 작거나 같은 자연수 이므로 map[][]의 크기는 그 2배인 28보다 크면 된다. 나는 30으로 했다 3) bfs의 스타트 지점은 상, 하, 좌, 우 로 14칸 가도 밖으로 안나갈 곳에서 시작한다. 나는 15, 15로 했다 4) 각 방향의 확률을 배열에 저장해 둔다. 5) 4방 탐색 bf..

www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 1) Queue를 2개 만들거임. 하나는 고슴도치, 하나는 물 2) 입력값을 받으면서 고슴도치가 나오면 queue에, 물이 나오면 queue2에 담는다. 동굴의 위치도 따로 저장한다. 3) bfs를 돌린다. 3-1) 고슴도치의 이동보다 물이 차는게 먼저다. 먼저 물을 채운다. (같은 너비를 다 채운후에 물을 채워야 한다) 3-2) 고슴도치의 이동경로를 queue에 담는다. 3-3) 동굴에 고슴도치가 도달하면 횟수(시간..

www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 풀이 1) 에라토스테네스의 체를 이용하여 1~9999 까지의 소수를 판별한 prime[] 을 만든다. 2) 입력받은 숫자A를 파라미터로 넣고 bfs를 돌린다. Queue의 제너릭 Node에는 숫자와 횟수를 담는다. 2-1) 숫자A를 StringBuilder에 담는다. (한 자리씩 치환하는것을 쉽게하기 위함) 2-2) 4자리이므로 4개만큼 for문을 돌리는데 숫자는 0~9까지이므로 10개만큼 for문을 또 돈다. 2-3)..

www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 1) 2차원 배열을 4개를 쓴다. 원본, 연합, 바꾼값, 방문체크 2) 2중 포문을 돌며 bfs를 도는것을 반복한다. 2-1) 연합끼리 분류한다. 2-2) 같은 연합이면 전부 평균값으로 바꾼다. 2-3) 원본과 비교한다. 2-4) 원본과 같으면 더이상 바꿀수 없는거임. while문을 탈출한다. 3) 2번을 2000번 돌린다. 4) 반복횟수를 출력한다. 주의사항 1) 없다 package com..