PS

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.첫째 줄

N×M크기의 배열로 표현되는 미로가 있다.미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.순열을

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터

케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호

문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을

다음과 같이 정의된 수열이 있다.D1 = ADn = Dn-1의 각 자리의 숫자를 P번 곱한 수들의 합예를 들어 A=57, P=2일 때, 수열 D는 {57, 74(=5^2+7^2=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37,

총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.1

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까

DFS와 BFS를 얼마나 기억하는지 자체적으로 테스트 하기 위해 지난번에 풀었떤 문제부터 다시 풀고 있다.전보다 생각하는 게 조금 간결해진 것 같다.STL은 다 까먹었지만!

전에 풀었던 것보다 코드는 간결해지고 문제 풀이 시간은 줄었다.

전보다 코드는 간결해지고 풀이 시간은 짧아졌다.

풀이

풀이

풀이

M개중 N개를 고르는 문제.넘겨줄 파라미터를 잘 골라야 하며 for 문 작성 시 주의

풀이

풀이

풀이 Tip

풀이

접근 DFS 문제이다. 대각선 방향으로 이동하며 해당 위치에 있는 디저트 번호를 확인한 뒤 방향을 바꾸거나 계속해서 같은 방향으로 가며 번호를 확인하는 과정을 반복한다. 이때 동일한 디저트 번호는 방문할 수 없는데, is_visit 배열을 이용하여 이를 구현하였다.

풀이

접근 시뮬레이션 (완전탐색) 문제이다. 가로 길이가 W인 벽돌에 최대 N번 구슬을 쐈을 때 남은 벽돌의 수를 비교하여 가장 적은 수를 출력해야 한다. 문제의 핵심은 완전탐색을 진행하면서 map을 가지고 가는 것이다. map을 2차원 배열 형식으로 선언했기 때문에 넘겨

접근 시뮬레이션 (완전탐색) 문제이다. 성능 테스트를 통과하면 현재 사용한 약품 개수가 최소인지 확인한 뒤 탐색을 종료한다. 그렇지 않을 경우, 현재 위치(d)에 약품처리를 한 뒤 탐색을 계속한다. 약품처리를 하기 전 상태 복구를 위해 현재 상태를 저장해야 한다.(p

먹을 수 있는 물고기 탐색이 포인트이다. (get_target())우선 모든 물고기에 대해 상어와의 거리를 구한다.그 다음 먹을 수 있는 물고기가 있다면 물고기의 정보를 반환한다.우선 모든 물고기의 거리를 -1로 세팅한다.bfs를 통해 도달 가능한 물고기의 거리를 up

문제 접근 상어가 물고기를 먹는다. 물고기는 번호가 작은 순서대로 차례로 움직인다. > 모든 물고기는 방향을 가지며, 한 칸을 움직일 수 있다. 범위 내에서(4x4), 이동하고자 하는 위치가 빈 공간이거나 다른 물고기가 있을 경우 이동 가능하다. 다른 물고기가 있을 경

문제 접근 시뮬레이션 문제이다. 모든 상어가 자신의 위치에 냄새를 뿌리고 시작한다. 1초마다 상어는 동시에 상하좌우로 인접한 칸 중 하나로 이동한 뒤 냄새를 뿌린다. 냄새는 1초에 1씩 사라지며 k시간 동안 유지된다. >이동 우선순위 정보를 저장하기 위해 각 상어의 구

문제 접근 시뮬레이션 문제이다. 문제 조건에 맞게 코드를 짜면 됨. 슬로퍼가 놓일 수 있는 다양한 경우의 수가 있는데 이를 규칙을 찾아 단순화 하는 것이 중요하다. 알고리즘 절벽지대의 정보를 입력 받아 활주로를 건설할 수 있는지 여부를 판단하게끔 하였다. 이때 가로,

시뮬레이션 문제문제에서 주어진 조건을 잘 이해하고 그대로 코딩하면 된다.뱀이 한 칸 이동했을 때 빈칸이라면 몸 길이가 1 줄어든다. 이를 큐를 이용하여 구현하였다. 즉, 뱀이 지나온 좌표 (pair<int, int>)를 큐의 원소로 삼았다.뱀이 좌표를 이동할 때마

시뮬레이션 문제이다.문제 흐름은 다음과 같다.모든 파이어볼을 방향으로 속력만큼 이동이동이 끝난 후, 같은 칸에 2개 이상의 파이어볼이 있다면모든 파이어볼을 하나로 합치고, 4개로 나눈다.관건은 범위 제한이 없는 격자를 구현하는 것!다음 위치가 격자 범위가 아니라면 sc

문제 접근 평소에 푸는 스타일대로 문제를 풀었더니 49개 테케까지만 통과되고, 시간 초과 오류가 발생했다. 배열 순회 대신 큐를 써서 BFS로 구현해야 겠다는 생각이 들었지만 아래 쟁점을 고려하기 힘들어서 참고를 많이 했다. 시간도 많이 썼다. 쟁점 활성화 세포가

줄기세포 배양 문제를 풀며 priority_queue 자료구조를 사용하는 문제를 풀어봐야겠다는 생각이 들어 예전에 푼 문제지만 다시 풀어보았다.예전 코드를 다시 보니 굉장히 주먹구구라 다시 풀어보길 잘 했다는 생각이 들었음.처음에는 prioirty_queue를 안 써서

시뮬레이션 문제이다. 주어진 조건에 맞추어 구현하면 됨.까다로웠던 점토네이도 구현총 길이가 1씩 늘어나는 토네이도를 구현할 때 복잡하게 생각했다. for문을 두 번 돌리면 되는 거였다.좌표 매핑토네이도가 방향을 바꿀 때마다 모래가 흩어지는데, 이 좌표를 하나하나 다 구

시뮬레이션 문제이다.다른 풀이를 찾아보니 귀찮아서 시도하지 않은 방법을 써서 코드를 더 예쁘게(?) 써놓은 게 있더라.웜홀 정보를 구조체로 따로 저장핀볼이 진행하는 방향에서 1~5번 블록을 만날 시 어떻게 꺾이는지 배열에 미리 저장내가 한 방법은 무식하고 직관적인 방법

시뮬레이션 문제이다.주사위가 상하좌우로 굴러갈 때만 잘 고려하면 크게 어려운 건 없었다.노트에 주사위가 한 칸 굴렀을 때의 숫자가 어떻게 변했는지 하나씩 그려 확인하는 노가다 작업이 필요했다.주사위 전면도에 임의의 순서를 붙였다. (1, 2, 4, 5, 6, 3) 순서

완전 탐색 문제이다.관건 1. 완전 탐색이 필요한 포인트모든 사람들이 계단을 내려가 이동이 완료되는 시간이 최소가 되는 경우를 찾아야 함.그러기 위해서는 '사람-계단' 의 모든 경우의 수에 대해 시뮬레이션을 해야 한다.따라서 '사람-계단' 쌍을 찾는 알고리즘을 dfs로

문제 접근 DFS를 활용한 시뮬레이션 문제이다. 관건1. 드래콘 커브의 규칙 찾기 K세대 드래곤 커브는 K-1세대 드래곤 커브가 그려진 방향을 뒤에서부터 꺼내 반시계 방향으로 90도 회전시킨 방향으로 한 획씩 그어가며 그려진다. 따라서 K세대 드래곤 커브를 그리기

문제 접근 완전탐색+BFS 문제이다. 관건1. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다. BFS는 M개의 바이러스를 선택한 뒤 실행된다. 여기서 선택하는 M개의 바이러스란 유일하게 활성 상태인 바이러스의 개수가 아니라,

문제 접근 완전탐색+BFS 문제이다. 문제 흐름 M개의 선거구 고르기 M(1 ~ N-1) 개의 선거구를 고른다. 선거구를 두 영역으로 나누는 문제를 한 영역에 포함시킬 선거구를 고르는 문제로 정의하여 해결. 해당 선거구가 가능한 방법인지 확인 각 영역이 연결되어

테르노미노찾아보니 DFS 문제라는데 나는 하드코딩으로 냅따 품.. 최적화란 없다.. 다시 풀어봐야겠다.

다리 만들기2길이가 2 이상꺾이면 안 된다.한 섬에 두 개의 다리 놓는 거 가능처음 생각: 그림대로라면 섬의 양 가쪽에 있는 땅으로부터 시작하는 게 낫다. 근데 섬의 양 가쪽을 어떻게 판별할 것인가에 대한 문제를 해결해야 한다.문제를 해결한 생각: 모든 땅덩어리에 다리

파이프 옮기기 1(1, 1) 에서 시작하여 (N, N) 까지 파이프를 옮기는 경우의 수를 찾는 문제완전탐색으로 풀어야 한다.방향은 (0) 오른쪽, (1) 대각선아래, (2) 아래쪽 으로 총 3가지가 존재한다.파이프는 정해진 방향으로만 밀 수 있다.정해진 방향이 의미하는

스타트 택시현재 택시의 위치에서 최단거리가 가장 짧은 승객부터 고르도록 한다.처음에 입력으로 주어질 때는 같은 위치에 있을 수 없을 것 같다.그리고 문제 조건 중 '모든 출발지는 서로 다르다' 라는 조건이 있기 때문에 출발지점이 같은 경우는 고려하지 않아도 된다.택시는

문제 컨베이어 벨트 위의 로봇 첫인상 문제가 잘 이해되지 않았던 문제. '건너편' 이 뭘 의미하는지 명확하게 제시되어 있으면 더 좋았을 것 같다. 질문 검색에 들어가니 문제 이해에 어려움을 겪는 사람이 나뿐만이 아니었던 것 같다. 제시된 그림과 내 머리속의 컨베이어