문제 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전..
알고리즘 풀이
문제 N×M의 모눈종이 위에 아주 얇은 치즈가 과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다. 와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, ..
Baekjoon_벽 부수고 이동하기 4 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다. 각각의 벽에 대해서 다음을 구해보려고 한다. 벽을 부수고 이동할 수 있는 곳으로 변경한다. 그 위치에서 이동할 수 있는 칸의 개수를 세어본다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 입력 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. 출력 맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 ..
헌내기는 친구가 필요해 (Baekjoon 21736) 문제 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다. 도연이가 다니는 대학의 캠퍼스는 N X M 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가 (x, y)에 있다면 이동할 수 있는 곳은 (x+1, y), (x, y+1), (x-1, y), (x, y-1)이다. 단, 캠퍼스의 밖으로 이동할 수는 없다. 불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해보자. 입력 첫째 줄에는 캠퍼스의 크기를 나타내는 두 정수 N..
문제 종현은 인생에서 한 번 있을 군 생활을 기념 겸 추억거리로 남겨두기 위해 증명사진을 찍어보았다. 그런데 웬걸! 사진관으로부터 받은 증명사진 속엔 대학생 상병 박종현이 아니라 세상 고초 다 겪은 직업 군인 중사 박종현이 찍혀있었다. 사진에 불만이 생긴 종현은 생활관 동기들에게 하소연 했지만, 동기들은 종현을 놀리기에 바빴다. 억울한 종현은 SNS에 이 사진이 정말로 자신과 닮았는지 공개 투표를 부쳐, 사진관에서 사진을 이상하게 편집했다고 주장하려고 한다. 투표는 백분율로 공개되고, 철회하거나 번복할 수 없다. 근성은 공개 투표가 친구가 많은 사람의 전유물이라고 생각했기 때문에, 감히 친구가 적은 종현이 SNS에 자신의 증명사진과 공개 투표를 올린 것을 용서하지 못한다. 하지만 근성의 생각과 달리 종현..
문제 민규와 친구들은 바로 옆에 붙어있는 두 빌라, 알파빌과 베타빌에 살고 있다. 이 두 빌라 중 알파빌은 싼값에 좋은 빌라라서 너무 인기가 많아 입주하려는 사람들이 줄을 선다. 민규의 친구들 역시 대기 번호를 받아 알파빌의 대기 명단에 적혀있다. 알파빌 입주에 실패한 친구들은 어쩔 수 없이 조금 더 비싼 베타빌에 들어가게 될 것이다. 이를 안타까워한 민규는 더 많은 친구를 알파빌에 입주시키기 위해 집주인 몰래 대기 명단을 바꾸려고 한다. 대기 명단에는 입주하려는 사람들의 대기 번호가 입주하는 순서대로 왼쪽에서 오른쪽으로 적혀 있으며, 대기 번호는 번부터 번까지의 서로 다른 정수이다. 민규는 한 번 명단을 바꿀 때 번호 두 개를 선택해서 서로 위치를 교환할 수 있다. 대기 명단을 너무 많이 바꾸면 집주인..
문제 N x N 크기의 2차원 배열이 있다. 2차원 배열의 i 행 j열에 해당하는 칸은 로 나타낸다. 처음에 이 배열의 각 칸에는 알파벳 대문자 또는 . 문자가 하나 적혀 있다. 상하좌우로 인접한 두 칸에 같은 문자가 적혀있는 경우, 두 칸은 연결되어 있다고 한다. 서로 연결된 칸들의 집합을 연결 요소라고 하고, 연결 요소의 크기는 그 연결 요소에 포함된 칸들의 개수와 같다. 구름이는 아래 작업을 Q번 수행하려고 한다. (y, x) 칸을 고른 뒤, 그 칸에 알파벳 대문자 를 쓴다. 구름이가 고른 칸은 . 문자가 적힌 칸임이 보장된다. 배열에 존재하는 모든 연결 요소의 크기를 계산한다. 만약 크기가 K 이상인 연결 요소가 존재한다면, 그 연결 요소에 포함된 모든 칸에 적힌 문자를 지운다. 모든 작업을 수행..
문제 플레이어는 1번부터 N번까지의 번호가 붙은 N개의 도시와 M개의 도로가 있는 나라에 살고 있다. 각 도로는 서로 다른 두 도시를 양방향으로 연결하고 있고, 주어진 도로만을 이용해 임의의 두 도시 사이를 이동하는 것이 가능하다. 플레이어는 차를 타고 S번 도시에서 E번 도시로 이동하려고 한다. 플레이어가 두 도시 사이를 이동할 때는 항상 가장 작은 수의 도시를 거치는 경로를 따라 이동한다. 예를 들어 아래 그림과 같이 도시와 도로가 주어지고, 플레이어가 1번 도시에서 4번 도시로 이동하려고 할 때는 항상 1 → 3 → 4의 경로를 따라 이동한다. 이 경우에는 출발 도시와 도착 도시를 포함해 총 세 개의 도시를 거쳐 이동할 수 있다. 1 → 5 → 2 → 4의 경로로 이동하는 것은 출발 도시와 도착 도..
문제 한 변의 길이가 N인 정사각형이 있다. 플레이어는 이 정사각형 위에 M개의 반직선을 그린 뒤, 두 반직선이 교차하는 점의 수를 세려고 한다. 플레이어가 반직선을 그리는 과정은 아래와 같다. 반직선을 그리기 시작할 칸 (y,x)를 정한다. (x,y)는 주어진 정사각형을 크기의 정사각형으로 나눴을 때,y 번째 행의 x번째 열에 해당하는 칸이다. 반직선을 그릴 방향 를 정한다. 방향은 상하좌우 중 하나이며, 항상 정사각형 테두리의 가로 혹은 세로와 평행하다. 반직선을 그린다. 반직선은 항상 시작 칸의 테두리에서부터 시작하며, 같은 칸을 지나는 평행한 직선이 서로 만나지 않도록 그린다. 풀이 def count_intersections(N, M, lines): vertical = [[0]*N for _ in..
문제 이 세상에는 수많은 컴퓨터들이 통신망을 통해 서로 연결되어 정보를 교류하고 있다. 오늘 플레이어는 이 거대한 통신망 중 한 구역을 조사하고자 한다. 플레이어가 조사할 구역에는 N개의 컴퓨터가 있고, M개의 통신 회선이 있다. 각 컴퓨터는 1번부터 N번까지 번호가 붙어 있고, 통신 회선은 서로 다른 두 컴퓨터를 양방향으로 연결하고 있다. 컴퓨터들은 연결 여부에 따라 여러 개의 컴포넌트로 나뉜다. 어떤 두 컴퓨터가 통신 회선만을 이용해서 연결되어 있다면 두 컴퓨터는 같은 컴포넌트에 속한다. 플레이어는 여러 개의 컴포넌트 중, 가장 밀도가 높은 컴포넌트를 조사하려고 한다. 컴포넌트의 밀도는 그 컴포넌트에 포함된 통신 회선의 개수를 컴퓨터의 수로 나눈 값이다. 주어진 통신 구역을 분석해서, 가장 밀도가 높..
