본문 바로가기

전체 글65

그래프 탐색 - 백준 14502 연구소 바이러스 문제인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 해설 1. DFS vs BFS ? 상관 없다. 바이러스를 퍼트릴 때 사용될 예정인데, 모든 벽이 아닌 노드를 방문할 수 있으면 된다.. 2024. 9. 27.
그래프 탐색 - 백준 18352 도시와 도로 문제어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.  이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다.  2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.  해설 1. BFS vs DFS ? BFS를 사용해 시작점으로부터 각 노드까지의 최단 거리를 구할 수 있.. 2024. 9. 27.
구현 - 프로그래머스 60062 외벽 점검 문제 후기어렵다.. 발상을 요하는 것 같다.  문제 설명레스토랑 외벽 중 취약 지점 몇 군데를, 몇 명이서 정해진 시간 내에 점검해야한다. - 동그란 모양이다.- 총 둘레 n 미터.- 사람 별로 이동 가능한 거리가 다름.- 최소한의 사람 수 구하기. 입력 예시1. 외벽 둘레인 n = 122. 취약 지점 위치 배열인 weak = [1,5,6,10]. 3. 사람별로 이동 가능한 거리 배열인 dist = [1,2,3,4]. 출력 예시1. 최소 사람 수인 2  모든 경우의 수한가지 경우의 수 동작 예시.사람을 ㄱ→ㄴ→ㄷ→ㄹ 순으로 배치.a 취약 지점에 ㄱ을 배치.한시간 뒤에 ㄱ이 b까지 점검할 수 있는지 확인된다면, b까지 점검할 수 있는지 확인된다면, c까지 점검할 수 있는지 확인안된다면, 다음 사람 ㄴ이 b.. 2024. 9. 20.
구현 - 백준 3190 뱀 #백준 3190https://www.acmicpc.net/problem/3190 문제 - 뱀이 있다.- 사과를 먹으면 길이가 늘어난다.- 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다. - N행 N열 보드판 위에서 진행된다.- 어떤 칸에는 사과가 있다.- 보드의 상하좌우 끝에는 벽이 있다.- 뱀은 1행 1열(0,0)에서 시작한다.- 뱀의 길이는 1이다.- 처음에는 오른쪽을 향한다. - 뱀은 1초마다 이동한다. - 이동 규칙은 다음과 같다.- 몸길이를 1 늘린다.- 머리를 다음칸에 위치시킨다.- 사과가 있다면, 사과가 없어진다. 몸 길이를 그대로 유지한다.- 사과가 없다면, 꼬리가 있었던 칸의 몸 길이를 줄인다.  - 이 게임이 몇 초에 끝나는지 계산한다. 입력 첫째 줄 : 보드 크기 N둘째 줄 : 사과 .. 2024. 9. 20.
구현 - 백준 18406 럭키 스트레이트 #백준 18406https://www.acmicpc.net/problem/18406 - 럭키 스트레이트라는 기술은 특정 조건을 만족할 때 사용할 수 있다. - 캐릭터의 현재 점수를 N이라 한다. - N을 자릿수 기준으로 반으로 나눈다. - 왼쪽 부분의 각 자릿수 합과 오른쪽 부분의 각 자릿수 합이 동일하면, 기술 사용의 조건을 만족한다. - 예시 점수 N = 123,402 - 기술 사용 조건을 만족한다면 "LUCKY"를 출력한다. - 기술 사용 조건을 만족하지 않는다면 "READY"를 출력한다. - N의 자릿수는 항상 짝수로 주어진다. 즉, 항상 반으로 나눌 수 있다. 입력 - 첫째 줄 :  123402 출력 - 첫째 줄 : LUCKY  접근  - 럭키 스트레이트라는 기술은 특정 조건을 만족할 때 사용할.. 2024. 9. 20.
미로 탈출 N*M 크기의 직사각형 형태의 미로에 갇혀있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다.현재 위치는 (1,1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다.  괴물이 있는 부분은 0, 괴물이 없는 부분은 1이다.  입력 예시 : 5 6101010111111000001111111111111 출력 예시 : 10 문제 분석 미로를 탈출하는 경로를 찾는 문제인데, 처음에 주어진 입력 예시만 보았을 때는 한 경로를  깊이 탐색하는 DFS를 써야만 한다고 생각했다. 이는 미로를 '탈출'한다는 경로의 관점에서 보아서 잘못 접근한 것이다. 단순히 미로를 탈출하는 것이 아니라, '최단 경로'를 통해 탈출해야 한다.하나의 경로에 깊숙히 들어갔다가 나와서 다시 다른 .. 2024. 9. 20.

티스토리툴바