[TIL_Carrotww] 110 - 23/04/28

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 백준 숨바꼭질2

브루트포스로 다 확인하는 줄 알았는데
잘 생각해보니 그냥 visited 써서 dfs, bfs 돌리면 답이 나올거같았다.
나는 bfs로 풀었다.

• 풀이

def solve():
    import sys
    from collections import deque

    N, K = map(int, sys.stdin.readline().split())
    visited = [0] * 100001

    def bfs(n, K):
        queue = deque()
        queue.append([n, 0])
        result = 0
        min_cnt = float('inf')

        while queue:
            cur_po, cnt = queue.popleft()
            if cur_po == K:
                if cnt < min_cnt:
                    min_cnt = cnt
                    result = 1
                elif cnt == min_cnt:
                    result += 1
                    continue

            for i in [cur_po-1, cur_po+1, cur_po*2]:
                if (i < 0 or i >= 100001) or (visited[i] != 0 and (visited[i] < visited[cur_po]+1)):
                    continue
                visited[i] = visited[cur_po] + 1
                queue.append([i, cnt+1])

        return [min_cnt, result]

    a, b = bfs(N, K)
    print(a)
    print(b)

if __name__ == "__main__":
    solve()

visited를 정해주고
bfs로 방문하는 좌표를 방문했는지, 지금 온 횟수보다 더 적은지를 체크하면서 돌아주면 된다.

🔍 백준 전쟁 전투

딱 문제를 보면 답이 나오는 문제다

• 풀이

def solve():
    import sys
    from collections import deque

    col, row = map(int, sys.stdin.readline().split())
    graph = []
    for _ in range(row):
        graph.append(list(sys.stdin.readline().strip()))

    visited_B = set()
    visited_W = set()

    result_B = []
    result_W = []

    dr, dc = [0, 0, 1, -1], [1, -1, 0, 0]

    def dfs_B(r, c):
        queue = deque()
        queue.append((r, c))
        visited_B.add((r, c))
        cnt = 1

        while queue:
            cur_r, cur_c = queue.popleft()
            for di in range(4):
                n_r, n_c = cur_r+dr[di], cur_c+dc[di]
                if (n_r < 0 or n_r >= row) or (n_c < 0 or n_c >= col) or ((n_r, n_c) in visited_B) or (graph[n_r][n_c] != "B"):
                    continue
                visited_B.add((n_r, n_c))
                queue.append((n_r, n_c))
                cnt += 1

        result_B.append(cnt**2)

    def dfs_W(r, c):
        queue = deque()
        queue.append((r, c))
        visited_W.add((r, c))
        cnt = 1

        while queue:
            cur_r, cur_c = queue.popleft()
            for di in range(4):
                n_r, n_c = cur_r+dr[di], cur_c+dc[di]
                if (n_r < 0 or n_r >= row) or (n_c < 0 or n_c >= col) or ((n_r, n_c) in visited_W) or (graph[n_r][n_c] != "W"):
                    continue
                visited_W.add((n_r, n_c))
                queue.append((n_r, n_c))
                cnt += 1

        result_W.append(cnt**2)

    for r in range(row):
        for c in range(col):
            if (r, c) not in visited_B and graph[r][c] == "B":
                dfs_B(r, c)

            if (r, c) not in visited_W and graph[r][c] == "W":
                dfs_W(r, c)

    print(sum(result_W), end=' ')
    print(sum(result_B))

if __name__ == "__main__":
    solve()

코드가 굉장히 긴데 함수 하나만써서 인자로 구별해주면 되는데 시간 정해놓고 풀다보니 이렇게 되어버렸다...ㅎ
기본 문제여서 그냥 안바꾸고 냅둠..

🔍 백준 A->B

범위를 정해주고 재귀 돌리면 될거같아서 풀었더니 됐다.
두 가지 방법으로 풀었는데 공간, 시간 제약이 빠듯하면 아마 첫 번째 풀이는 안 풀릴수도 있다.
근데 어지간해서는 될듯??
이 문제 다른사람들이 푼게 궁금해서 찾아보니 다른사람들은 풀이가 다 비슷비슷하다.
몇사람이 풀고 그거 다 배껴간듯...?
내가 푼것 치고 깔끔하게 푼거같다 ㅎㅎ

• 첫 번째 풀이

def solve():
    import sys
    A, B = map(int, sys.stdin.readline().split())
    result = []

    def dfs(num, cnt):
        if num > B:
            result.append(-1)
            return
        if num == B:
            result.append(cnt)
            return

        dfs(int(str(num)+str(1)), cnt+1)
        dfs(num*2, cnt+1)

    dfs(A, 1)

    answer = -1
    for i in result:
        if i != -1:
            answer = i
            break

    print(answer)

if __name__ == "__main__":
    solve()

1을 붙여주는 연산과 두배를 하는 연산에서 변수가 갱신되면 어쩌지 해서 다 result list에 때려 박았다.

코드가 이쁜것 같지가 않아서 개선한 풀이가 다음 풀이이다.

• 두 번째 풀이

def solve():
    import sys
    A, B = map(int, sys.stdin.readline().split())

    def dfs(num, cnt, min_cnt):
        if num > B:
            return min_cnt
        if num == B:
            return min(cnt, min_cnt)

        min_cnt = dfs(int(str(num)+str(1)), cnt+1, min_cnt)
        min_cnt = dfs(num*2, cnt+1, min_cnt)

        return min_cnt

    result = dfs(A, 1, B+1)

    if result == B+1:
        print(-1)
    else:
        print(result)

min_cnt 변수를 담길때 작은 값으로 갱신해주면 깔끔하게 풀 수 있다.
굿