수학과의 개발자 도전기

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

정답 풀이 

두 보물 간의 거리 중 최댓값을 구하는 문제다. 근데 두 보물의 위치가 정확히 나온 것은 아니고, "보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다." 문구에서 처럼 두 보물의 위치는 상황마다 달라서 매번 구해야 한다. 이는 모든 육지지점(L)에 대해서 bfs로 탐색 후 가장 긴 길이 중 최댓값을 출력하라는 걸로 이해했다. 

1. 주어진 행렬에서 모든 L 지점을 시작으로 bfs를 진행한다.

2. 지나온 칸 개수를 visit에 기록하고, 각 케이스에서 visit의 최댓값을 result에 추가한다.

3. max(result) - 1 값을 출력한다. (두 지점 간의 거리를 출력하기 때문에 1을 뺐다. 1 안 빼면 틀린다!) 

# python3 - 시간 초과, pypy3 - 성공 하는 코드
def bfs(i, j, visit):
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    queue = [[i, j]]
    visit[i][j] = 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 < m:
                if matrix[nx][ny] == 'L' and not visit[nx][ny]:
                    visit[nx][ny] = visit[x][y] + 1
                    queue.append([nx, ny])
                    
        
n, m = map(int, input().split())
matrix = [list(input()) for _ in range(n)]

result = []
for i in range(n):
    for j in range(m):
        if matrix[i][j] == 'L':
            visit = [[0] * m for _ in range(n)]
            bfs(i, j, visit)
            answer = 0
            for k in range(n):
                answer = max(answer, max(visit[k]))
            result.append(answer)
            
            
print(max(result) - 1)

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

처음에는 어떻게 풀어야할지 감이 잘 잡히지는 않았는데, 문제에서 "체스판을 칠하는 경우의 수는 왼쪽 가장 위를 검정색, 흰색으로 칠하는 2가지 경우이다." 문구에 힌트를 얻었다. 결국 (0, 0) 값이 검정, 흰색이냐에 따라 체스판 모양이 정해지는 것이기 때문에 주어진 행렬을 8 x 8 로 탐색하면서 두 가지 경우의 체스판과 비교하면서 정답인 체스판과 다른 정사각형의 개수를 각각 구해 그 중에서 최솟값을 출력하면 되겠다 라고 생각했다. 

정답 풀이

위 생각을 단계별로 정리하면 다음과 같다. 

1. (0,0)이 검정으로 시작하는 black, 흰색으로 시작하는 white 행렬 미리 만들어 두기

2. 주어진 n x m 행렬(matrix) 8 x 8 단위로 for문 돌리기

3. 8 x 8 행렬의 각 원소값을 black 체스판, white 체스판과 비교하면서 다른 정사각형의 개수를 각각 black_count, white_count에 +1 하기

4. 8 x 8 행렬 탐색이 끝나면 answer = min(answer, black_count, white_count) 진행

5. 모든 단계가 끝나면 answer 최종 출력

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

matrix = [list(input()) for _ in range(n)]
first = ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B']
second = ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W']

black = []
white = []
for i in range(8):
    if i % 2 == 0:
        black.append(second)
        white.append(first)
    else:
        black.append(first)
        white.append(second)
        
answer = 1e9
for i in range(n - 7):
    for j in range(m - 7):
        black_count = 0
        white_count = 0
        for k in range(8):
            for l in range(8):
                if matrix[i + k][j + l] != black[k][l]:
                    black_count += 1
                if matrix[i + k][j + l] != white[k][l]:
                    white_count += 1
                    
        answer = min(answer, black_count, white_count)        
    
print(answer)

- 링크 : www.acmicpc.net/problem/4485

이 문제는 bfs로 진행하는데 각 노드에는 숫자가 있다. 각 노드를 지날 때마다 노드 값이 더해지는데, (0,0)에서 (n - 1, n - 1)까지 가면서 지나간 노드의 값의 최솟값을 구하는 문제다.

바로 bfs문제라는 것은 떠올랐지만, 다음 노드로 넘어갈 때 최소값인 경우를 고려해야하기 때문에 heap을 이용한 다익스트라를 구현해야함은 떠오르지 않았다. 다익스트라는 몇 번을 풀어도 머리에 잘 안 남는 것 같다 흑ㅠ

1. distance(n x n 크기) 행렬 이용하기

문제를 풀면서 잘 안 풀렸던 부분은 heap을 이용해야하는 것은 알겠는데, 그럼 heappop 값이 상하좌우에 있는 값이 아닌 저 멀리 떨어진 값이 나오면 어떻게 구분할 수 있을지 잘 몰랐다. 아래 코드에서도 확인되겠지만, 최댓값(1e9)로 이루어진 distance 행렬을 이용하면 된다. 

2. 노드 재방문 여부는 체크하지 않아도 된다.

경로를 지나다가 방문했던 노드를 지나는 게 최단 경로가 된다면 그냥 지나가도 되기 때문에 visit 행렬로 따로 방문 여부를 체크하지 않아도 된다. 최종 목표는 목표 지점까지 최솟값으로 가는 것이다!

정답 풀이

import heapq 

def dijkstra() :
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    queue = [[matrix[0][0], 0, 0]]
    distance = [[INF] * n for _ in range(n)]
    distance[0][0] = 0
    
    while queue:
        value, x, y = heapq.heappop(queue)

        if x == n - 1 and y == n - 1:
            print("Problem {0}: {1}".format(index, distance[x][y]))
            break
            
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                new_value = value + matrix[nx][ny]
                
                if new_value < distance[nx][ny]:
                    distance[nx][ny] = new_value
                    heapq.heappush(queue, [new_value, nx, ny])

INF = 1e9
index = 1 
while True : 
    n = int(input())
    
    if n == 0:
        break
    
    matrix = [list(map(int, input().split())) for _ in range(n)]
    
    dijkstra()
    index += 1

Reference

참고 블로그 : https://bbbyung2.tistory.com/60

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

문제 이해 

- 주어진 행렬에서 가장 바깥에 있는 치즈(값이 1인 칸)를 모두 한 번에 지워가면서 (1) 모두 사라지기 전 치즈 칸의 개수와 (2) 다 사라지기 까지의 시간을 구하는 문제다. 

- 일단 (1) 모두 사라지기 직전 치즈 칸의 개수를 출력하기 위해 초기 1의 개수(count)를 모두 구한 다음에 한 시간씩 치즈가 사라질 때마다 그 개수를 count에서 빼주면서 진행하면 된다. 모두 사라졌을 때는 count를 감소 시키는 단계가 없기 때문에 그대로 count를 출력하면 된다.

- (2) 시간은 bfs를 진행하는 횟수로 세면 된다. 

- 일단 바깥 치즈의 위치를 큐에 저장한 뒤, 탐색이 끝나면 그때 큐에 저장한 치즈를 모두 제거한다. (그때그때 치즈를 제거하면 바깥에 있지 않은 다른 치즈가 제거될 수 있기에 바깥 치즈를 모두 모았다가 한 번에 제거해야 한다)

- 대충 이렇게 까지는 그려졌는데, 가장 어려웠던 부분이 바깥 치즈의 위치를 구하는 것이었다. 1을 기준으로 근처에 0이 있는 걸로 하면, 내부에 구멍이 있는 경우도 해당되기 때문에 어떻게 해야할지 감이 안 잡혔다. 

- 그래서 풀이를 찾아보았더니, 값이 0인 (0, 0)에서 시작해 0을 기준으로 탐색을 하면 된다는 거다. 0을 기준으로 시작해 움직이다가 만나는 1은 바깥에 있는 값이다. 그리고 0을 만나면 이를 큐에 넣어서 탐색을 진행하면 된다. 바깥에 있는 1의 값은 melt에 넣고, 0은 queue에 넣어서 bfs를 진행하면 된다. 

- 그 외는 bfs 기본 로직이다. 

-> 가장 바깥에 있는 1을 구하는 방법 기억하자!!!!

정답 풀이 

from collections import deque

def bfs():
    queue = deque() # 값이 0인 좌표
    queue.append([0, 0])
    melt = deque()  # 가장 바깥에 있는 치즈 좌표
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and not visit[nx][ny] :
                visit[nx][ny] = 1
                if cheese[nx][ny] == 0:
                    queue.append([nx, ny])
                elif cheese[nx][ny] == 1:
                    melt.append([nx, ny])
    for x, y in melt:
        cheese[x][y] = 0
    return len(melt)
                
    
n, m = map(int, input().split())

cheese = []
count = 0 # 나중에 모두 없어지기 한 시간 전 치즈 칸 개수 세기 위함
time = 1
for i in range(n):
    data = list(map(int, input().split()))
    cheese.append(data)
    for j in range(m):
        if data[j] == 1:
            count += 1   

dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
while True:
    visit = [[0] * m for _ in range(n)]
    melt_count = bfs()
    count -= melt_count
    if count == 0:
        print(time)
        print(melt_count)
        break
    time += 1

참고 블로그

Python-백준-2636-치즈-BFS