240318 [BOJ/백준] 31575. 도시와 비트코인

 

31575번: 도시와 비트코인 (acmicpc.net)

31575번: 도시와 비트코인

---

나의 코드

1. bfs사용

def bfs(x, y):
    q.append([x, y])
    visited[x][y] = 1

    while q:
        a, b = q.pop(0)
        if a == m - 1 and b == n - 1:
            return 'Yes'

        for k in range(2):
            ni = a + di[k]
            nj = b + dj[k]

            if 0 <= ni < m and 0 <= nj < n and arr[ni][nj] == 1 and visited[ni][nj] == 0:
                visited[ni][nj] = 1
                q.append([ni, nj])
    return 'No'


n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(m)]
visited = [[0]*n for _ in range(m)]
di = [0, 1]  # 우,하 방향설정
dj = [1, 0]
q = []

print(bfs(0, 0))

 

2. dfs 사용

def dfs(x,y):
    global ans
    visited[x][y] = 1

    if x == m-1 and y == n-1:
        ans = 'Yes'
        return
        
    for k in range(2):
        ni = x + di[k]
        nj = y + dj[k]

        if 0 <= ni < m and 0 <= nj < n and arr[ni][nj] == 1 and visited[ni][nj] == 0:
            visited[ni][nj] = 1
            dfs(ni, nj)

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(m)]
visited = [[0]*n for _ in range(m)]
di = [0, 1]  # 우,하 방향설정
dj = [1, 0]
ans = 'No'

dfs(0, 0)
print(ans)

 

결과

.

---

출력은 나오는데 계속 틀림...ㅎㅎ 그것도 dfs랑 bfs 두가지 방법으로 풀어보겠다고 욕심내다가 둘 다 틀렸다. 그 이유는! 거래소가 자기가 서있는 곳은 체크 못하도록 내가 코드를 짰기 때문이었다. 내가 if문을 ni와 nj가 m-1과 n-1일 때 yes값이 나오도록 했는데 그래도 자기 자신이 서있는 곳 (0,0)을 체크할 수 있다고 생각했다.그래서 97프로까지 갔는데 틀렸나보다ㅜㅜ 틀렸습니다가 많은 이유는 bfs와 dfs 둘다 그렇게 짰기 때문이라고 위안삼아야지! 그 이후에 파이참 안돌리고 바로 수정하다가 컴파일에러랑 런타임에러 다 맞아봤다...ㅎㅎ 그 덕에 UnboundLocalError를 알게 되었는데 그건 전역변수를 함수 안에서 지역변수처럼 쓰려고 했기 때문이란다. 그건 또 if문을 visited 밑에 x와 y를 m-1과 n-1일 때 yes값이 나오도록 해서다. if문의 위치에 따라 답이 맞을수도 틀릴수도 있다는 것을 명심하자!! 쉽게 풀거라고 생각했던 문제, 어렵게 해결....ㅎㅎ