수학과의 개발자 도전기

- 문제 : https://www.acmicpc.net/problem/1697

문제 이해 

- 현재 위치(x)에서 동생이 있는 위치에 가는 3가지 방법(x - 1, x + 1, 2 * x)으로 이동한다.

- 이동할 때 1초가 걸리는데, 3가지 방법으로 1초에 칸을 이동하므로 bfs를 이용해서 진행한다. 

- 여기서는 2차 행렬이 아닌 1차 배열인 arr를 이용해서 방문여부 + 걸리는 시간을 저장한다. 

풀이 로직

- 최대 숫자가 10만이므로 number를 10만으로 설정한 뒤 배열 arr를 만든다. 시작하는 n은 중복해서 가면 안되므로 arr[n] = 1 처리한다.

- bfs를 진행하는데, 도착한 지점이 k라면 arr[k] - 1을 출력한 뒤 루프를 break 한다.

arr[k] - 1을 하는 이유는 처음에 arr[n] = 1로 시작하지만 시간은 0초이므로 시간과 배열값이 1 차이가 나기 때문이다.

정답 풀이 

from collections import deque

n, k = map(int, input().split())

number = 10 ** 5
arr = [0 for _ in range(number + 1)]
arr[n] = 1
queue = deque()
queue.append(n)
while queue:
    x = queue.popleft()
    if x == k :
        print(arr[x] - 1)
        break
        
    for i in [x - 1, x + 1, 2 * x]:
        nx = i
        if 0 <= nx <= number and arr[nx] == 0:
            arr[nx] = arr[x] + 1
            queue.append(nx)

- 문제 : https://www.acmicpc.net/problem/2583

문제 이해 

- 좌표로 주어지는 영역을 제외한 부분 중에 독립된 영역의 개수와 각 영역의 크기를 출력하는 문제다.

- 일단 사각형 넓이만큼 행렬을 채운 뒤 나머지 빈 영역을 bfs로 탐색하면 된다고 이해했다. 

- 전반적으로 쉬운 문제였지만 좀 어려웠던 부분이 주어진 좌표를 행렬 인덱스로 변경하는 것이었다. 

풀이 로직 

- 기본 값을 받은뒤 주어진 (x1, y1), (x2, y2) 좌표를 가지고 matrix에 영역을 1로 채운다.

- 행렬을 채우는 코드는 다음과 같은데 하나의 사각형은 행 (m - y2) ~ (m - y1), 열 x1 ~ x2 의 영역을 차지한다. 

for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split()) # 좌표 (x1, y1)은 (m - y1)행 x1열
    for i in range(m - y2, m - y1):
        for j in range(x1, x2):
            matrix[i][j] = 1

- 주어진 x1, y1, x2, y2를 바로 사용하지 않은 이유는 좌표와 행렬 인덱스의 구조가 다르기 때문이다.

아래 그림으로 이해해보면 행렬은 (0,0)이 왼쪽 위인 반면에 좌표는 (0,0)이 왼쪽 아래다. 그래서 좌표에서 x좌표는 열을 의미하고, y좌표는 행을 의미한다. 또한 열은 행렬과 좌표 모두 동일하지만 행의 경우 거꾸로 되어있어서 (행렬 가로길이 - y좌표)값이 좌표를 행렬로 바꾼 것이다. 

- matrix에 각 사각형을 채웠으면 방문하지 않고, matrix 값이 0인 지점들을 기준으로 bfs를 실행한다. 

- 영역의 전체 개수와 각 영역의 넓이를 출력한다. (전체 개수도 출력해줘야 한다. 문제를 잘 읽자!)

정답 풀이 

m, n, k = map(int, input().split())
matrix = [[0] * n for _ in range(m)]
visit = [[0] * n for _ in range(m)]

for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split()) # 좌표 (x1, y1)은 (m - y1)행 x1열

    for i in range(m - y2, m - y1):
        for j in range(x1, x2):
            matrix[i][j] = 1

def bfs(x, y, visit, matrix):   
    queue = [[x, y]]
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    count = 1
    while queue: 
        x, y = queue.pop(0)
        visit[x][y] = 1
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < m and 0 <= ny < n:
                if not visit[nx][ny] and matrix[nx][ny] == 0:
                    count += 1
                    visit[nx][ny] = 1
                    queue.append([nx, ny])
    return count    

answer = []
for i in range(m):
    for j in range(n):
        if not visit[i][j] and matrix[i][j] == 0:
            answer.append(bfs(i, j, visit, matrix))
            
answer.sort()
print(len(answer))
for i in range(len(answer)):
    print(answer[i], end = ' ')

- 문제 : https://www.acmicpc.net/problem/2468

문제 이해

- 비가 h가 높이만큼 오면 높이가 h 이하인 건물은 물에 잠기는데, 잠기지 않는 영역(비 높이 < 건물 높이)을 구하는 문제다. 

- 비의 높이가 따로 주어지지 않았으므로 비가 오는 높이의 모든 경우의 수를 고려해야한다. (비가 오지 않는 높이 0부터 건물의 최대 높이까지 진행한다)

- 비 높이 초과인 건물들의 영역을 구하면 그게 안전영역이므로 bfs를 1번만 진행한다. (비가 와서 잠긴 영역을 처리하고, 잠기지 않은 영역을 bfs로 구하면 bfs를 중복으로 연산하므로 효율적이지 않기 때문)

풀이 로직

- 건물 높이 정보를 입력받는다. 이때 건물의 최대 높이를 max_height 변수에 저장한다. rain은 비가 오는 높이다. 

- 비가 오지 않는 경우(rain == 0) 부터 최대로 오는 경우(rain == max_height)까지 반복문을 돌면서 그때마다 bfs를 진행한다.

- 방문하지 않은 지점 중에 잠기지 않는 건물(높이 > rain)이 있다면 그 건물을 중심으로 영역을 탐색한다.

- 각 비가 오는 높이에 따라 잠기지 않는 영역 개수를 temp로 계산한뒤 그때그때마다 최대값을 answer에 저장한다.

- 반복문을 나오면 answer의 값이 최대이자 정답이므로 answer를 출력한다.

정답 풀이 

n = int(input())

matrix = []
max_height = 0
for _ in range(n):
    arr = list(map(int, input().split()))
    max_height = max(max_height, max(arr))
    matrix.append(arr)

def bfs(x, y, visit, matrix, rain):
    queue = [[x, y]]
    visit[x][y] = 1
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    while queue:
        x, y = queue.pop(0)
        
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n :
                if not visit[nx][ny] and matrix[nx][ny] > rain:
                    visit[nx][ny] = 1
                    queue.append([nx, ny])
        
    
answer = 0   
for rain in range(max_height + 1):
    temp = 0 # rain 높이에도 잠기지 않는 영역 
    visit = [[0] * n for _ in range(n)]
    for x in range(n):
        for y in range(n):
            if not visit[x][y] and matrix[x][y] > rain:
                bfs(x, y, visit, matrix, rain)
                temp += 1                
                
    answer = max(answer, temp)    
    
print(answer)

- 문제 : https://www.acmicpc.net/problem/7562

문제 이해 

- bfs의 기본 로직을 따르는 문제이고, 다른점은 움직이는 방향이 상하좌우 4가지가 아닌 대각선 방향으로 총 8가지의 움직임이 있다는 것이다. 

- 현재 있는 위치를 기준으로 움직이는 방향을 계산해서 directions 배열로 진행한다. 

풀이 로직 

- 전체 행렬 크기 n과 시작점 [a, b]와 도착지 [c,d]를 입력 받는다. 

- 방문여부를 확인과 몇 칸을 이용했는지 알기 위해 visit를 이용하는데, 시작점인 [a, b]의 visit 값은 1로 두고 시작한다. 

- visit 값이 0이면 방문하지 않은 지점이라 지나가면 되고, 1 이상이면 이미 방문한 지점이라 건너뛰면 된다. 

- while문으로 bfs를 진행하는데 도착한 지점이 목적지인 [c, d]라면 더 진행할 필요가 없으므로 루프를 break 한다. 
- 이전 지점에서 한 칸 움직이므로 visit[nx][ny] = visit[x][y] + 1로 설정한다.

- visit 행렬을 지나온 칸 수로도 사용하지만, 방문 여부로도 사용해서 정답값 + 1 형태이다. 그래서 visit[c][d] - 1을 출력한다. 

(시작점인 [a, b]에 있을 때 이동한 칸 수는 0이지만, visit[a][b] = 1 이기 때문)

정답 풀이 

import sys
from collections import deque
input = sys.stdin.readline

directions = [[-2, -1], [-1, -2], [-2, 1], [-1, 2], [1, -2], [2, -1], [2, 1], [1, 2]]

for _ in range(int(input())):
    n = int(input())
    a, b = map(int, input().split())
    c, d = map(int, input().split())
    # [a, b] 에서 [c, d]로 몇 번 만에 가는지 
    
    queue = deque()
    queue.append([a, b])
    visit = [[0] * n for _ in range(n)]
    visit[a][b] = 1 
    while queue:
        x, y = queue.popleft()
        if x == c and y == d:
            break
        
        for i in range(8):
            nx, ny = x + directions[i][0], y + directions[i][1]
            if 0 <= nx < n and 0 <= ny < n:
                if not visit[nx][ny]:
                    visit[nx][ny] = visit[x][y] + 1
                    queue.append([nx, ny])
                    
    print(visit[c][d] - 1)