swanzzz 님의 블로그

[오늘의 문제]https://www.acmicpc.net/problem/1600[오늘의 학습 키워드]너비 우선 탐색구현그래프 탐색, 그래프 이론격자 그래프1. 문제설명 동물원을 탈출한 원숭이가 0, 0 좌표에 존재합니다. 이 원숭이가 N, M 좌표로 이동하려고 하는데 말이 되고 싶어 말처럼 이동이 가능합니다. 말처럼 이동하는데는 최대 K번 이동이 가능하고 그 이후에는 인접한 4방향으로 이동이 가능합니다. 격자판에 정보가 주어질 때, 원숭이가 최소한의 동작으로 0, 0 좌표에서 N, M 좌표로 이동하는 방법을 구하는 문제 입니다.[제한사항]시간 제한 2초메모리 제한 256MBN과 M은 1이상 200이하의 자연수K는 0이상 30이하의 정수격자판에 주어진 정보 0은 평지, 1은 장애물2. 접근방식이 문제를 해..

[오늘의 문제]https://www.acmicpc.net/problem/4179  [오늘의 학습 키워드]BFS1. 문제 설명지훈이가 미로에서 탈출하려고 합니다. 미로에 탈출구는 가장자리에 접한 공간으로 탈출이 가능합니다. 미로에는 불이 났고 지훈이가 미로에서 불타기 전에 탈출할 수 있다면 탈출에 걸린 시간을, 탈출이 불가능한 경우 IMPOSSIBLE을 출력하는 문제입니다. 지훈이와 불은 대각선으로 이동할 수 없습니다. 즉 delta 4방향으로만 이동이 가능하다는 의미입니다.[제한사항]시간 제한 1초메모리 제한 256MB1 ≤ R, C ≤ 1000# 벽. 지훈이가 이동 가능한 공간J 지훈이의 초기 위치F 불이 난 공간J 는 입력에서 하나만 주어집니다.2. 접근 방식여기서 주의할 점은 J는 입력에서 하나만 ..

[오늘의 문제]https://www.acmicpc.net/problem/17471[오늘의 학습 키워드]백트래킹, BFS, 조합1. 문제 설명백준시는 N개의 구역으로 나뉘어져 있고, 구역은 1번부터 N번이 존재합니다. 구역을 두개의 선거구로 나뉘어 투표를 진행하려고 하는데 지역에 존재하는 사람수가 최대한 적게 차이가 나게 만드려고 합니다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구로 포함된 지역은 모두 연결되어 있어야 합니다.위 그림을 볼때 3번 그림이 불가능한 이유는 1, 2, 3, 4 지역은 연결되어 있어서 하나의 선거구로 볼 수 있는데 5, 6은 서로 떨어져 하나의 선거구로 볼 수 없기 때문입니다. 공평하게 선거구를 나누는 방법을 구하는 문제입니다.[제한사항]시간 제한 0.5초메모리 제한..