지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 MN 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 88 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8x8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8x8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
N, M = map(int, input().split()) board = [list(input().rstrip()) for _ inrange(N)]
defcheck_BW(slice_board): # print(slice_board) black_cnt = 0# black 시작 [bwbwbwbw],[wbwbwbwb] for row inrange(8): for col inrange(8): if (row % 2 == 0and col % 2 == 0) or (row % 2 == 1and col % 2 == 1): if slice_board[row][col] != "B": black_cnt += 1 if (row % 2 == 0and col % 2 == 1) or (row % 2 == 1and col % 2 == 0): if slice_board[row][col] != "W": black_cnt += 1
white_cnt = 0# white 시작 [wbwbwbwb],[bwbwbwbw] for row inrange(8): for col inrange(8): if (row % 2 == 0and col % 2 == 0) or (row % 2 == 1and col % 2 == 1): if slice_board[row][col] != "W": white_cnt += 1 if (row % 2 == 0and col % 2 == 1) or (row % 2 == 1and col % 2 == 0): if slice_board[row][col] != "B": white_cnt += 1
returnmin(black_cnt, white_cnt)
check = [] for row inrange(N - 7): for col inrange(M - 7): cnt1, cnt2 = 0, 0 # 체스판 경우의 수 slicing c = [board[row + i][col:col + 8] for i inrange(8)] # c = [c[(0 + col):(8 + col)] for c in board[(0 + row):(8 + row)]] check.append(check_BW(c)) print(min(check))
M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍은 한 번만 센다.
두 우주 A와 B가 있고, 우주 A에 있는 행성의 크기는 A1, A2, …, AN, 우주 B에 있는 행성의 크기는 B1, B2, …, BN라고 하자. 두 우주의 행성 크기가 모든 1 ≤ i, j ≤ N에 대해서 아래와 같은 조건을 만족한다면, 두 우주를 균등하다고 한다.
Ai < Aj → Bi < Bj
Ai = Aj → Bi = Bj
Ai > Aj → Bi > Bj
입력
첫째 줄에 우주의 개수 M과 각 우주에 있는 행성의 개수 N이 주어진다. 둘째 줄부터 M개의 줄에 공백으로 구분된 행성의 크기가 한 줄에 하나씩 1번 우주부터 차례대로 주어진다.
space_list = [list(map(int, input().split())) for _ inrange(M)]
new_space_list = [[] for _ inrange(M)] dictionary = {} for i inrange(M): new_list = sorted(list(set(space_list[i]))) for j inrange(len(new_list)): dictionary[new_list[j]] = j for x in (space_list[i]): new_space_list[i].append(dictionary[x])
new_space_list.sort() cnt, ans = 1, 0 for i inrange(1, M): if new_space_list[i] == new_space_list[i - 1]: cnt += 1 else: ans += cnt * (cnt - 1) // 2 cnt = 1
M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍은 한 번만 센다.
두 우주 A와 B가 있고, 우주 A에 있는 행성의 크기는 A1, A2, …, AN, 우주 B에 있는 행성의 크기는 B1, B2, …, BN라고 하자. 두 우주의 행성 크기가 모든 1 ≤ i, j ≤ N에 대해서 아래와 같은 조건을 만족한다면, 두 우주를 균등하다고 한다.
Ai < Aj → Bi < Bj
Ai = Aj → Bi = Bj
Ai > Aj → Bi > Bj
입력
첫째 줄에 우주의 개수 M과 각 우주에 있는 행성의 개수 N이 주어진다. 둘째 줄부터 M개의 줄에 공백으로 구분된 행성의 크기가 한 줄에 하나씩 1번 우주부터 차례대로 주어진다.
space_list = [list(map(int, input().split())) for _ inrange(M)]
new_space_list = [[] for _ inrange(M)] dictionary = {} for i inrange(M): new_list = sorted(list(set(space_list[i]))) for j inrange(len(new_list)): dictionary[new_list[j]] = j for x in (space_list[i]): new_space_list[i].append(dictionary[x])
count = 0 for i inrange(M - 1): for j inrange(i + 1, M): if new_space_list[i] == new_space_list[j]: count += 1
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
입력
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.
토마토가 하나 이상 있는 경우만 입력으로 주어진다.
출력
여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
N, M = map(int, input().split()) # matrix 배열 matrix = [list(map(int, input().rstrip())) for _ inrange(N)]
# 이동할 네 방향 정의 (상,하,좌,우) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1]
# BFS 소스코드 구현 defbfs(x, y): # 큐(Queue) 구현을 위해 deque 라이브러리 사용 queue = deque() queue.append((x, y)) # 시작점 (0,0) # 큐가 빌 때까지 반복하기 while queue: x, y = queue.popleft() # 현재 위치에서 4가지 방향으로의 위치 확인 for i inrange(4): nx = x + dx[i] ny = y + dy[i]
# 미로 탐색 공간 내에서만 if0 <= nx < N and0 <= ny < M: # 벽이 아닌경우 if matrix[nx][ny] == 1: queue.append((nx, ny)) matrix[nx][ny] = matrix[x][y] + 1 # 가장 오른쪽 아래까지의 최단 거리 반환 return matrix[N - 1][M - 1]
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
![[백준] 1018번 체스판 다시 칠하기](/images/posts/thumb/baekjoon.png)
