수학과의 개발자 도전기

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

문제 이해 

- bfs를 이용해서 1이 모여있는 각 영역의 크기 중에서 가장 큰 값을 출력하는 문제다. 

- 음식물의 주어진 위치 n, m 값이 1부터 시작하기 때문에 n -= 1, m -= 1을 하지 않으면 IndexError가 발생한다. 

풀이 로직 

- 행렬 세로, 가로, 음식물의 개수를 입력받는다. 

- matrix에 음식물의 위치를 행 - 1, 열 - 1 위치에 1로 입력한다.

- matrix를 완전 탐색하면서 방문하지 않고, 음식물인 (matrix[i][j] == 1) 위치를 중심으로 bfs를 진행한다.

- 각 bfs를 실행할 때마다 영역의 크기를 count로 센 다음 마지막에 count를 반환하면 된다. 

- 각 count 값 중에서 최댓값을 찾아서 출력하면 정답

정답 풀이 

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

for _ in range(k):
    a, b = map(int, input().split())
    matrix[a - 1][b - 1] = 1

def bfs(x, y, matrix, visit):
    queue = [[x, y]]
    visit[x][y] = 1
    count = 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 not visit[nx][ny] and matrix[nx][ny] == 1:
                    visit[nx][ny] = 1
                    count += 1
                    queue.append([nx, ny])
    return count 

answer = 0
for i in range(n):
    for j in range(m):
        if not visit[i][j] and matrix[i][j] == 1:
            answer = max(answer, bfs(i, j, matrix, visit))
            
print(answer)

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

문제 이해 

- 이전 숨바꼭질 문제와 최소 이동시간 구하는 것은 동일한데, 최소 경로에 지나는 노드들을 출력하는 점이 다른 문제다. 

- 최소 시간은 동일해서 어렵지 않았지만, 경로를 어떻게 출력해야할지 잘 몰랐다. 

- 경로는 bfs의 특징을 이해해서 풀면 되는데, bfs를 수행하는 과정에서 현재 위치(부모 노드)를 다음 이동할 위치(자식 노드) 인덱스에 표시한다. (예 : check[자식노드] = 부모노드)

-> check를 이용하면 리프노드부터 위로 올라가면서 그 부모노드들을 찾을 수 있다.

풀이 로직 

- check 리스트는 수빈이가 다음으로 이동할 위치 인덱스에 현재 위치를 표시해주는 역할 (예 : check[자식노드] = 부모노드)

- move 함수는 이동 경로를 출력하는 함수이고, k부터 시작해 n까지 가는 경로를 진행하기 때문에 이를 거꾸로 바꿔서 출력한다.

- bfs를 진행하다가 k에 도착한 경우 최소 시간을 출력한 뒤 move()를 실행해 경로를 출력한다. 

- 아직 k에 도착하지 않았다면 x - 1, x + 1, 2 * x로 진행하면서 (1) 범위내에 있고, (2) 방문하지 않은 노드들로 탐색한다. 

- 노드를 방문처리한 뒤, queue에 넣는다. 이때 x가 부모이고 nx가 자식이므로 check[nx] = x 도 처리해준다. 

정답 풀이 

from collections import deque

def move(now):
    data = []
    temp = now
    for _ in range(visit[now] + 1):
        data.append(temp)
        temp = check[temp]        
    print(' '.join(map(str, data[::-1])))
    
    
def bfs():
    queue = deque()
    queue.append(n)
    while queue:
        x = queue.popleft()
        if x == k:
            print(visit[x])
            move(x)
            return 
        
        for nx in [x - 1, x + 1, 2 * x]:
            if 0 <= nx <= 10 **5 and not visit[nx]:
                visit[nx] = visit[x] + 1
                queue.append(nx)
                check[nx] = x
    
n, k = map(int, input().split())
number = 10 ** 5
visit = [0] * (number + 1)
check = [0] * (number + 1)
bfs()

참고 블로그 : https://data-flower.tistory.com/79

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

Gold Lv5 이고, 스스로 푼 문제다. 

문제 이해 

- 기존에 풀었던 숨바꼭질 문제와 비슷한데 다른 점은 x -> 2 * x로 이동할 때 시간이 걸리지 않는다는 점이다.

- 이렇게 이동했을 때 n에서 k로 이동하는데 걸리는 최소 시간을 출력하는 문제다. 

- 이동할 때 시간을 추가하는 거는 분기문으로 나눠서 진행하면되는데

- 문제는 2 * x 로 이동하는데 시간이 걸리지 않으므로 visit했던 노드들도 다시 방문할 경우 시간이 최소가 될 수 있다는 것이다. 

그래서 이부분을 따로 처리해줘야지 틀리지 않는다. 

풀이 로직 

- 입력값을 받고, arr를 설정한다. 이때 arr는 10 ** 5 보다 크게해야지 IndexError가 발생하지 않는다. 

- arr값이 0이면 방문하지 않은 지점이고, 0이 아니라면 이전에 방문한 적이 있는 지점이다. 

- x - 1, x + 1, 2 * x 만큼 이동한 nx로 bfs를 진행한다. 

- 이 때 처음 방문하는 노드 (arr[nx] == 0)인 경우에는 방문 처리 후 queue.append(nx) 처리를 해주면 된다.

- 만약 이전에 방문한 노드를 마주쳤다면 (arr[nx] != 0) arr의 값이 최소값인 형태로 변경해주면 된다. 

if nx == 2 * x:
	arr[nx] = min(arr[nx], arr[x])
else:
	arr[nx] = min(arr[nx], arr[x] + 1)

- queue가 빌 때까지 진행한다음에 arr[k] - 1을 출력한다. (arr[k]가 1로 시작하기 때문에 정답이랑 1 차이가 난다)

정답 풀이 

from collections import deque

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

number = 2 * 10 ** 5
arr = [0] * (number + 1)
arr[n] = 1

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

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

문제 이해

- 이전에 풀었던 숨바꼭질 문제에서 최소 시간으로 도착하는 경우의 수를 출력하는 것이 추가된 문제다. 

- 경우의 수를 구하는 게 살짝 어려웠다. 

풀이 로직

- 이차 행렬인 visit를 이용해서 방문여부와 경우의 수를 기록하면서 전체 bfs를 진행한다.

- 다음 노드가 처음 방문하는 노드인 경우는 경우의 수가 동일하고, 다음 노드가 이전에 방문한 노드인 경우에는 경우의 수를 합친다. 

- bfs가 끝나고 난뒤 도착점이 k에서의 최소시간과 경우의 수를 출력한다. 

정답 풀이 

골드 문제중에 2차 행렬을 이렇게 설정하는게 있는데 이 부분이 부족해서 익숙하지 않은 것 같다. 여러번 연습이 필요한 것 같다. 

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

number = 10 ** 5
visit = [[-1, 0] for _ in range(number + 1)] # [도착까지 걸리는 시간, 경우의 수]

queue = [n]
visit[n][0] = 0 
visit[n][1] = 1
while queue:
    x = queue.pop(0)
        
    for nx in [x - 1, x + 1, 2 * x]:
        if 0 <= nx <= number:
            if visit[nx][0] == -1: # 처음 방문하는 지점이면
                visit[nx][0] = visit[x][0] + 1 
                visit[nx][1] = visit[x][1] # 경우의 수는 동일함
                queue.append(nx)
            elif visit[nx][0] == visit[x][0] + 1: # 다음 노드가 이전에 방문한 노드인 경우 + 최단 시간으로 도착한 경우
                visit[nx][1] += visit[x][1] # 경우의 수 합치기
            
print(visit[k][0])
print(visit[k][1])

참고 블로그 : [백준] 12851번: 숨바꼭질4