문제 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 풀이 가로, 세로와 3 X 3 영역을 확인하여 스도쿠 퍼즐에 채워지지 않은 숫자 중 알맞은 숫자를 채우는 문제이다. 채워지지 않는 곳은 0으로 제시된다. 따라서 0인 부분의 좌표를 찾고 해당 좌표에 어떤 값을 대입하면 되는지 확인하면 된다. 확인하는 방법은 다음과 같다. 한 행에 어떤 값이 없는지 확인한다. 한 열에 어떤 값이 없는지 확인한다. 그래프의 행/열을 전환시켜 확인하면 쉽다. 3 X 3 영역에 어떤 값이 없는지 확인한다. 코드 from sy..
백준: 16933 벽 부수고 이동하기 3
문제 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 문제 풀이 앞서 다룬 문제인 벽 부수고 이동하기 2 문제에서 낮에만 벽을 부술 수 있고, 밤에는 벽을 부술 수 없다는 조건이 추가된 문제이다. 문제를 풀기 위해서는 토마토 문제와 같이 하루에 발생할 수 있는 모든 경우의 수를 처리하여야 하므로, day 2 추가된 경우의 수가 3이라면 하루 동안 처리 되도록 하여야 한다. 이는 큐의 길이만큼 처리하는 방식을 사용하면 된다. 코드 from sys import stdin from..
문제 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 문제 풀이 앞서 다룬 벽 부수고 이동하기 문제에서 경우의 수가 K로 추가된 문제이다. 해당 문제에서는 입력되는 K에 따라 벽을 부 술 수 있는 횟수가 증가하게 된다. 따라서 경우의 수는 벽을 부순 횟수가 (0, 1, ... K)로 증가된 문제이다. 벽 부수고 이동하기 코드에서 K에 대한 경우의 수를 추가해주면 해결 할 수 있다. (단, PyPy3로 제출하여야 시간 내에 통과할 수 있다.) 코드 from sys import ..
문제 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 문제 풀이 그래프를 탐색하는데 이동할 수 없을 경우 벽 하나를 부수고 탐색을 이어갈 수 있다. 즉, 벽 하나를 부술 경우 가장 최단 경로로 (N, M)에 도착하는 경우를 반환하는 문제이다. 보통 최단 거리를 구할 때, 2차원 배열을 생성하여 이동한 거리를 중첩시켜며 앞으로 나아가며 목적지에 도착한 경우 탐색을 종료한다. 문제에서는 벽을 부순 경우와 부수지 않은 경우 2가지의 경우의 수가 존재하기에 기존에 거리를 중첩하는 방식이 ..
연구소 시리즈 연구소 연구소 2 연구소 3 문제 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net 문제 풀이 연구실에 바이러스가 유출되었고, 벽을 3개 설치할 수 있을 때 가장 많은 안전지대를 확보한 경우를 찾는 문제이다. 문제를 풀기 위해서는 FloodFill과 같이 바이러스가 있는 지점으로부터 상, 하, 좌, 우로 전파가 가능한지 확인하여 바이러스가 전파될 것이다. 토마토 문제와 유사하지만 다른 점은 벽을 세워야 한다는 것이다. 따라서 다음과 같은 경우의 수를 구하여 문제를 해결 할 수 있다. 백트랙킹을 통해 3개의 벽..
문제 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 문제 풀이 N * N 체스판 내에 데스 나이트가 r1, c1에 있을 때, r2, c2에 방문가능 한지를 판단하는 문제이다. 데스 나이트는 문제에 주어진 것과 같이 6가지 방향으로 움직일 수 있다. 따라서 한 정점으로 부터 방문할 수 있는 모든 경우의 수는 시도 횟수 1로 생각하여야 한다. 데스 나이트가 방문할 수 있는 모든 정점을 다 방문하여도, r2, c2에 도달하지 못한 경우는..
문제 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 N * N의 체스판이 주어졌을 때, 서로 공격할 수 없도록 퀸을 배치할 수 있는 경우의 수를 찾는 문제이다. 해당 문제의 경우 다음과 같은 경우의 수를 판단하여 백트랙킹을 하면 된다. 같은 행 또는 열에 다른 퀸이 존재하는가? 행의 경우 DFS를 통해 재귀호출을 하게 되면 하나의 행에 대한 선택을 진행하므로 별도로 확인할 필요는 없다. 열의 경우 예를 들어, 첫번째 퀸의 자리가 (0, 0)이라면 같은 열에 있는지 확인해 주어야 한다. 우측 상단에서 좌측 하단(↙..
백준: 14225 부분수열의 합
문제 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 � www.acmicpc.net 문제 풀이 이 문제는 주어진 수열의 부분 합을 구하였을 때, 구할 수 없는 수를 반환하는 문제이다. 예제 입력 1에서 구할 수 있는 경우의 수를 트리로 벗는다면 위의 그림과 같다. 즉 주어진 수열을 모두 선택하는 경우와 부분적으로 선택하지 않을 때에 따라 합을 구하면 되는 것이다. 이를 코드로 구현한다면 재귀 호출을 이용하면 쉽게 구할 수 있다. 코드를 작성하기 위해서는 다음과 같은 경우..
