CEO

문제 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문�� www.acmicpc.net 문제 풀이 특정 지점을 시작으로 같은 색을 가진 싸이클이 있는지 확인하고 반환하는 문제이다. 따라서 특정 지점에서 DFS를 통해 상, 하, 좌, 우로 순회하되 같은 출발 지점과 같은 색인지와, 방문여부를 판단하게 되면 싸이클 여부를 확인 할 수 있다. DFS를 통해 탐색할 때 다음과 같이 진행하면 답을 찾을 수 있다. 상, 하, 좌, 우 탐색 시 0

문제 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 문제 풀이 그래프의 연결 정보가 주어질 때, 이분 그래프인지 판단하여 이분 그래프읜 경우 'YES' 아닌 경우는 'NO'를 반환하는 문제이다. 문제를 풀기 위해 이분 그래프에 대한 이해가 필요하다. 이분 그래프를 만족하기 위해서는 2가지 조건이 필요하다. 첫 번째로 한 정점에서 다른 정점으로 연결된 경우, 서로 다른 그룹이어야 한다. 두 번째, 모든 그룹은 2개로 나뉘어야 한다는 조건이 있다. 문제의 예제 입력 1은 테스트 케이스가 1, 2로 ..

문제 7562번: 나이트의 이동 문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 www.acmicpc.net 문제 풀이 앞서 다룬 2178 미로 탐색과 동일한 방식으로 풀면 된다. 차이점이 있다면 탐색하는 방향이 대각선 8 방향이라는 것뿐이다. 나이트가 이동할 수 있는 경로로 이동할 때, 현재 경로까지 오는데 이동한 횟수를 계속 누적해가며 이동하면 된다. 따라서 원하는 도착 위치에 도착했을 때 중첩된 값이 찾고자 하는 답이다. 코드 from sys import stdin from collections import deque def visitable(x, y): r..

문제 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 문제 풀이 익은 토마토와 안 익은 토마토가 인접해있다면 상, 하, 좌, 우로 한 칸씩 영향을 받아 토마토가 익게 된다. 상자에 토마토들의 정보가 주어졌을 때, 모든 토마토가 익는데 걸리는 날짜를 계산하여 반환하면 된다. 위의 그림은 예제 입력 1이다. 예제 입력 1의 경우 토마토가 익는데 걸리는 시간은 8일이 소요된다. 이는 우측 하단에 있는 익은 토마토를 기준으로 그림과 같이 하루가 지남에 따라 대각선 방향으로 토마토들이 익기 때문이다...

문제 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 풀이 시작 지점(0, 0)에서 도착 위치에 갈때까지 몇칸을 이동해야 하는지 찾는 문제이다. 시작 지점 부터 상, 하, 좌, 우로 탐색하면서 인접한 칸 중에 방문 가능한 칸이 있는지 확인 후에, 값을 중첩시키며 도착 위치에 이르렀을 때 몇칸을 이동했는지 출력하면 된다. 위으 그림과 같이 예제 입력1, 2를 탐색하게 되면 도착 지점에 이르기까지 값을 중첩하면 답을 구할 수 있는 것을 알 수 있다. 처음에는 백트랙킹이 필요하지 않을까 생각했는데 그럴 필요 없이 값을 누적하며 탐색을 진행하..

문제 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사 www.acmicpc.net 문제 풀이 주어진 지도에서 섬의 개수를 찾는 문제이다. 2667 단지번호붙이기와 유사한 문제이지만 경우의 수가 추가된 문제이다. 상하좌우뿐 아니라, 대각선으로 인접한 경우도 같은 섬으로 판단한다. 즉, 위의 그림과 같이 하나의 점에서 총 8방향으로 탐색을 진행하면 된다. 코드 from sys import stdin from collections import deque def visitable(x, y): return 0

문제 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 문제 풀이 지도에서 영역을 탐색하여 단지가 몇 개인지 확인하는 문제이다. 단지를 확인 하기 위해서는 BFS를 통해 다음과 같은 조건을 확인하며 탐색을 진행하면 된다. 모든 시작점을 확인하기 위해 2중 반복문으로 N * N 만큼의 시작점을 탐색한다. 시작점이 단지(1인 경우)라면 시작점을 기준으로 상, 하, 좌, 우로 탐색하여 연결된 집이 있는지 확인한다. 지도 내에 위치하는지 확인 하기 위해 0

문제 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 풀이 그래프 탐색을 통해 연결된 관계에서 다음과 같은 관계를 이루는 경우가 있는가를 찾는 문제이다. DFS를 탐색 하는데 있어 시작 지점을 각 노드로 지정하여 탐색을 하면 된다. 백트랙킹이 필요하므로, `vistied` 체크/해제를 진행해주어야 정상적으로 경우의 수를 찾을 수 있다. A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 즉, 이는 DFS로 탐색할 경우 depth가 4보다 큰 경우가 있는지를 찾는 것과 같다. 5명이 친구 관계를 이루어야 하지만 depth가 4인 경우까지만 찾으면 되는 이유는 depth가 0인 경우, 즉..