코딩 공부하는 코딩류

토마토들이 완전히 익으려면 며칠이 걸리는지 계산하는 문제 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알..

치즈가 다 녹는 데 몇 시간 걸리는 지 구하는 문제 문제 N×M (5≤N, M≤100)의 모눈종이 위에 아주 얇은 치즈가 과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다. 와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 ..

하나였던 빙산이 녹아서 쪼개지는 데 최소 몇 년이 걸리는지 구하는 문제 문제 지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다. 2 4 5 3 3 2 5 2 7 6 2 4 그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보 빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 ..

모눈종이에 색칠되지 않은 영역의 갯수와 넓이를 구하는 문제 문제의 조건 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다. 와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다. M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로..

적록색약이 아닌 사람이 보는 세상과 적록색약인 사람이 보는 세상이 얼마나 다른지 구하는 문제 문제의 조건 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에 RRRBB GGBBB BBBRR BBRRR RRRRR 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1) 그림이 입력으..

비가 내렸을 때 물에 잠기지 않을 지역의 최대 갯수를 구하는 문제 문제의 조건 1. 어떤 지역의 높이 정보가 위와 같이 주어진다. 2. 비가 4만큼 오면 위와 같이 높이가 4 이하인 지역은 모두 물에 잠긴다. 3. 이 때 하얀 부분을 물에 잠기지 않는 안전 영역이라 할 수 있는데 같은 안전 영역의 범위는 상하좌우로 맞닿은 영역들만 포함한다. 즉 이런 경우처럼 대각선 방향으로 맞닿아 있는 영역은 같은 안전 영역이라 할 수 없다. 2번의 경우에서 안전 영역의 갯수는 5개이다. 4. 6만큼 비가 와서 높이가 6 이하인 지역이 모두 물에 잠긴다면 위와 같이 나타낼 수 있다. 이 때 안전 영역의 갯수는 4개이다. 이 지역에서 비가 오는 양 별로 안전 영역의 갯수를 모두 확인해 봤을 때 최대 갯수는 5개이다. 5...

지도에 표시되어 있는 섬의 개수를 세는 문제 문제의 조건 1. h의 높이 x w의 너비 크기를 가진 지도가 주어진다. 2. 2차원 지도 배열에는 0과 1로 표시가 되어 있다. 0은 바다, 1은 땅이라는 뜻 3. 2차원 배열의 각 땅들은 상하좌우 대각선으로 연결되면 하나의 섬이라고 할 수 있다. 4. 여러 테스트 케이스가 주어질 때 각 테스트 케이스의 섬의 갯수를 구해서 출력하기 5. 입력의 마지막 줄에는 0 0 이 주어진다. 입력받은 w와 h가 둘 다 0이라면 테스트 케이스 입력받기 종료하고 프로그램도 종료 풀이 과정 BFS로 상하좌우에 연속되어 있는 같은 숫자 갯수 세던 문제에서 대각선 방향만 추가해서 풀면 될 거 같아서 기존 BFS 코드에 대각선 방향만 추가해서 풀었습니다. 1. 방향 확인용 배열에 ..

방향이 없는 연결 그래프에서 서로서로 연결된 덩어리가 몇 개인지 구하는 문제 문제의 조건 1. 첫째 줄에 N개의 정점을 가진 양방향 연결 그래프와 M개의 간선이 주어진다. 2. 둘째 줄부터 간선의 양 끝점이 주어진다. 3. 서로 연결된 요소가 몇 개인지 출력 풀이 과정 앞전에 풀었던 컴퓨터 바이러스 문제처럼 몇 개의 정점이 간선을 통해 서로 연결되어 있는지 확인하면 될 거라고 생각했습니다. 연결 요소라는 말이 헷갈렸는데 질문 게시판 보니까 컴퓨터 바이러스 문제처럼 간선으로 서로서로 연결된 것들을 한 덩어리로 치는 것이 맞더라고요. 풀이 1. 양방향 그래프를 만든 뒤 BFS로 현재 정점에서 방문할 수 있는 곳들을 모두 방문한다. 2. 1번 과정이 끝나고 나면 한 연결 요소(덩어리) 탐색이 끝난 것이기 때문..