너비우선탐색

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하기 인구 이동은 하루 동안 다음과 같이 진행, 인구 이동이 없을 때까지 지속 국경선을 공유하는 인접한 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다. 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다. 연합을 이루고 있는 각 칸의 인구수는..

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 요약 현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하기 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 벽을 부수면, 빈 방과 동일한 방으로 변한다. 제한사항 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. N개의 줄에는 미로의 상태를 ..

https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳, 1은 벽이 있는 곳을 나타낸다. (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 최단 경로로 이동하려 한다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다. 첫째 줄에 ..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳, 1은 벽이 있는 곳을 나타낸다. (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 최단 경로로 이동하려 한다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 첫째 줄에 최단 거리..

https://school.programmers.co.kr/learn/courses/30/lessons/169199 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 격자모양 게임판 위에서 말을 움직이는데, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다 중간에 G가 나와도 장애물이 아니므로 그냥 지나치게 됨 (문제에는 이 말이 없어서 처음에 이거 이해 못했음) "."은 빈 공간을, "R"은 로봇의 ..

https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 그래프 탐색 문제이다. 처음에는 입력에서 주어진 좌표로 가능한 범위로 그래프를 만들어서 탐색을 돌려야 하나 생각했었다. 하지만 좌표 자체를 한 정점으로 생각하고 정점 간 탐색을 해주면 됐었다. 0. 입력받을 때 편의점의 좌표를 Dot이라는 객체 배열에 저장한다. 1. 상근이네 집을 시작으로 BFS 탐색을 한다. 2. 락페에 도착할 수 있는지 검사를 한다.(맨하탄 거리가 1000이하여야 한다...