윤만석

문제 도현이가 사는 도시는 N×M 크기의 모양이며, 1×1칸으로 나누어져 있다. 각 칸은 빈 칸 또는 벽이다. 도현이는 학교에 가려고 한다. 도현이가 있는 곳은 항상 빈 칸이고, 학교도 빈 칸에 있다. 도현이는 현재 있는 칸과 상하좌우로 인접한 칸으로 이동할 수 있다. 이때, 벽이 있는 칸으로는 이동할 수 없다. 또, 도시를 벗어날 수는 없다. 준규는 도현이가 학교에 가지 못하게 빈 칸을 적절히 벽으로 바꾸려고 한다. 이미 벽인 곳은 벽으로 바꿀 수 없고, 빈 칸만 벽으로 바꿀 수 있다. 도현이와 학교가 있는 곳은 벽으로 바꿀 수 없다. 도현이가 학교에 가지 못하게 하기 위해서 빈 칸을 벽으로 바꿔야하는 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 세로 크기 N과 가로 크기 M이..

문제 N개의 나라가 있고, 이들 중 몇 개의 나라들은 서로 도로로 연결되어 있다. 편의상 N개의 나라들은 각각 1, 2, ..., N의 번호가 붙어 있다고 하자. i번 나라와 j번 나라가 도로로 연결되어 있으면 i번 나라에서 j번 나라로 이동할 수 있고, j번 나라에서 i번 나라로도 이동할 수 있다. 당신은 1번 나라에 살고 있다. 여름을 맞이하여 당신은 N번 나라로 왕복 여행을 다녀오려고 한다. 즉 1번 나라에서 N번 나라로 갔다가 다시 1번 나라로 돌아오고자 한다. 아쉽게도 각 도로의 이용권이 한 장씩밖에 주어져 있지 않아서, 한 번 지난 도로는 다시 지날 수 없다고 한다. 이때, 여행에 소요되는 최소 시간을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 나라의 개수 N과 도로의 개수 M이 주어진다...

문제 N개의 도시가 P개의 양방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 한다. 성실한 이석원은 두 도시 사이를 최대한 많이 왔다 갔다 하려 하는데, 이때 한 번 방문했던 도시(1, 2번 도시 제외)를 두 번 이상 방문하지 않으려 한다. 한 번 1번 도시와 2번 도시 사이를 오갈 때, 반드시 한 개 이상의 도시를 중간에 거쳐야 한다. 입력에는 1번 도시와 2번 도시를 연결하는 길은 없다. 도시의 번호는 1번부터 N번까지이다. 입력 첫째 줄에 두 정수 N(3 ≤ N ≤ 400), P(1 ≤ P ≤ 10,000)이 주어진다. 다음 P개의 줄에는 각 길이 연결하는 서로 다른 두 도시의 번호가 주어진다. 출력 첫째 줄에 왔다 갔다 할 수 있는 최대 횟수를 출력한다. 네트워크..