swanzzz 님의 블로그

[오늘의 문제]https://www.acmicpc.net/problem/2146[오늘의 학습 키워드]너비 우선 탐색BFS구현그래프 탐색, 그래픈 이론격자 그래프1. 문제설명 좌표평면에 지도의 정보가 주어집니다. 0은 바다, 1은 육지를 의미할 때 현재 육지와 다른 육지를 잇는 다리를 놓으려고 합니다. 이 다리를 놓을 때 가장 적은 비용이 들도록 가장 짧은 다리 하나만 설치한다고 합니다. 육지와 다른 육지를 잇는 다리의 길이가 가장 짧은 경우를 구해 출력하는 문제 입니다.[제한사항]시간 제한 2초메모리 제한 192MBN(100이하의 자연수)0은 바다, 1은 육지항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.2. 접근방식 문제를 보면 육지와 다른 육지를 잇는 최대한 짧은 다리를 놓으려 합니다. 그..

[오늘의 문제]https://www.acmicpc.net/problem/2206[오늘의 학습 키워드]BFS1. 문제 설명 N x M 행렬의 미로를 탈출하는 문제입니다. 0은 이동이 가능한 길1은 이동이 불가능한 벽을 의미하는데 벽은 1번 부술수 있습니다. 모든 경로중 가장 짧은 경로를 찾아서 이동 시간을 출력하는 문제입니다.만약 탈출이 불가능한 경우 -1을 반환합니다.[제한 사항]시간 제한 2초메모리 제한 192MB1 ≤ N ≤ 1,0001 ≤ M ≤ 1,0002. 접근 방식 전형적인 BFS 문제 같습니다. 벽을 부술수 있을 때 이동 가능한 모든 경로를 queue에 넣어서 다음 위치를 탐색합니다. 그 중 벽을 부숴야 하면 부수고 이동한 뒤 그 상태를 queue에 넣어서 종료까지 탐색을 실시합니다. 한가지..