문제: 효율적인 해킹 (백준 1325번)문제 분석N개의 컴퓨터와 M개의 신뢰 관계가 주어질 때, 한 컴퓨터를 해킹하면 그 컴퓨터를 신뢰하는 다른 컴퓨터들도 해킹할 수 있다.각 컴퓨터를 시작점으로 하여 해킹할 수 있는 컴퓨터의 수(직접 및 간접)를 구한 뒤, 가장 많은 컴퓨터를 해킹할 수 있는 노드를 출력하는 문제이다. 접근입력으로 주어지는 (a, b) 관계는 "a가 b를 신뢰한다"는 의미이므로,b를 해킹하면 a도 해킹할 수 있다.이를 위해, 각 노드에 대해 역방향 그래프를 구성하여, 해당 노드에서 출발해 도달할 수 있는 노드의 수를 구하면 된다.해결 방법그래프 구성:입력 (a, b)를 받으면, graph[b]에 a를 추가한다.→ 이렇게 하면 b를 해킹했을 때, a로 확산되는 효과를 모사할 수 있다.BFS..

문제: 맥주 마시면서 걸어가기 (백준 9205번)문제 분석편의점에서 맥주를 최대 20병까지 들고 이동할 수 있으며, 50m마다 한 병을 마셔야 한다. 따라서 한 번에 이동할 수 있는 최대 거리는 1000m이다.출발지에서 도착지까지 이동 가능한지를 판단하는 문제로, 노드를 방문하면서 연결된 곳을 탐색하는 BFS를 사용하면 해결할 수 있다.해결 방법각 장소(출발지, 편의점, 도착지)를 노드로 보고, 이동 가능한 거리(1000m 이하)라면 간선을 연결해 그래프를 구성한다.이후 BFS를 이용해 출발지에서 도착지까지 도달할 수 있는지 탐색한다.노드 정의Node 구조체를 정의해 위치 (x, y)와 간선 정보를 저장한다.operator- 연산자를 오버로딩하여 두 지점 사이의 맨해튼 거리(절댓값 거리)를 계산할 수 있..

문제: 보물섬(백준 2589번)문제 분석지도 상에 있는 땅('L')과 물('W')이 주어질 때, 모든 땅에서 출발하여 가장 멀리 떨어진 땅까지의 최단 거리를 구하는 문제다. 즉, 모든 땅을 시작점으로 BFS를 수행하여 최대 이동 거리를 계산한 후 그 중 가장 큰 값을 출력하면 된다.문제의 핵심은 다음과 같다.BFS를 사용해 각 땅에서의 최대 거리를 계산맵 상에서 땅('L')에서 시작해 상하좌우로 이동하며, 각 칸까지 도달하는 최소 이동 횟수를 구한다.모든 땅을 시작점으로 탐색물('W')는 탐색 대상이 아니므로 건너뛴다.최대 이동 횟수를 찾는다.BFS역할:주어진 시작점에서 BFS를 수행하여, 도달할 수 있는 모든 땅까지의 최단 거리를 계산하고, 그 중 최대 거리를 반환한다.동작:depth 배열을 통해 각 ..

문제: 탈출 (백준 3055번)문제 분석출발 지점부터 도착 지점까지 최단 거리를 구하는 문제인데, 매 이동마다 물에 잠기는 구간이 늘어난다. 맵이 물에 잠기는 시간에 따른 시뮬레이션과, 출발 지점부터 도착 지점까지의 이동 경로를 구하는 과정을 따로 처리해야 한다. 언뜻 보면 단순한 시뮬레이션 문제로 보이지만, 실제로는 맵이 물에 잠기는 시간을 계산하는 BFS와, 출발 지점부터 도착 지점까지의 최단 거리를 구하는 BFS를 두 번 수행하면 쉽게 계산할 수 있다. 먼저 보드(board)를 입력받는다. 보드는 r×c 크기의 2차원 배열로, 각 칸에 문자('S', 'D', '*', '.', 'X')가 주어진다.'S'는 시작 지점, 'D'는 도착 지점, '*'는 물, 'X'는 바위(갈 수 없는 구역), '.'은 빈..

문제: 스타트링크 (백준 5014번)문제 분석스타트링크라는 고층 건물에는 총 f층이 있고, 현재 s층에 있는 사람이 g층으로 가야 한다. 엘리베이터에는 위로 u층, 아래로 d층만 이동할 수 있는 버튼이 있다. 주어진 조건 내에서 최소한으로 버튼을 눌러 목표 층에 도착해야 한다. 만약 도착할 수 없다면 "use the stairs"를 출력해야 한다.핵심 아이디어BFS 큐 초기화현재 층(s)을 큐에 삽입하고, visited 벡터를 활용해 방문한 층과 해당 층까지의 버튼 누른 횟수를 기록했다.층 이동 로직큐에서 노드를 꺼낸 뒤:위로 이동: 현재 층 + u가 건물의 총 층수 f를 넘지 않으면서 방문한 적이 없다면 큐에 추가.아래로 이동: 현재 층 - d가 1층 이상이면서 방문한 적이 없다면 큐에 추가.종료 조건..

파이프 옮기기 문제 정리 및 풀이문제 개요파이프 옮기기 1: nn의 최대 크기가 16으로, 단순한 탐색 알고리즘으로도 풀이 가능.파이프 옮기기 2: nn의 최대 크기가 32로, 단순 탐색은 시간 초과 발생.두 문제는 기본적인 로직은 동일하지만, 입력 크기에 따라 효율적인 접근 방식이 필요하다. 파이프 옮기기 1 (탐색 방식)탐색 방식으로 모든 경로를 BFS로 탐색하여 풀이한다.탐색할 때 파이프의 세 가지 상태(가로, 대각선, 세로)를 기준으로 이동 가능 여부를 판단한다.코드 설명BFS 탐색queue를 이용해 파이프의 현재 상태를 관리한다.이동 가능한 위치를 계산하고, 조건을 만족하는 경우 dpdp 배열에 이동 경로를 추가한다.결과 출력dp[n−1][n−1]dp[n-1][n-1]: 도착점까지의 경로 수 출..