728x90
난이도 : 실버3
풀이일 : 11223
https://www.acmicpc.net/problem/26169
링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐
오답 코드
import sys
board = [list(map(int, sys.stdin.readline().split())) for _ in range(5)]
x, y = list(map(int, sys.stdin.readline().split()))
di, dj = [-1, 1, 0, 0], [0, 0, -1, 1]
flag = False
visited = [[False] * 5 for _ in range(5)]
def DFS(i, j, depth, apple):
global flag
visited[i][j] = True
if board[i][j] == 1:
apple += 1
if apple == 2:
flag = True
return
if depth > 2:
return
for k in range(4):
ni, nj = i + di[k], j + dj[k]
if 0 <= ni < 5 and 0 <= nj < 5:
if board[ni][nj] != -1 and not visited[ni][nj]:
DFS(ni, nj, depth + 1, apple)
return
DFS(x, y, 0, 0)
if flag:
print(1)
else:
print(0)
- 한 번 방문했던 곳에 대해 visited 초기화 작업을 해주지 않아 문제 발생
- 아래는 이 코드로 틀렸던 반례
- 0 1 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0
풀이코드
import sys
board = [list(map(int, sys.stdin.readline().split())) for _ in range(5)]
x, y = list(map(int, sys.stdin.readline().split()))
di, dj = [-1, 1, 0, 0], [0, 0, -1, 1]
flag = False
visited = [[False] * 5 for _ in range(5)]
def DFS(i, j, depth, apple):
global flag
visited[i][j] = True
if board[i][j] == 1:
apple += 1
if apple == 2:
flag = True
return
if depth > 2:
return
for k in range(4):
ni, nj = i + di[k], j + dj[k]
if 0 <= ni < 5 and 0 <= nj < 5:
if board[ni][nj] != -1 and not visited[ni][nj]:
DFS(ni, nj, depth + 1, apple)
visited[ni][nj] = False
DFS(x, y, 0, 0)
if flag:
print(1)
else:
print(0)
- DFS로 깊이 세 번 이내에 사과를 두 번 먹는 경우가 있는지 탐색
- 사과를 두 번 먹는 경우를 찾으면, flag를 True로 변경
- 최종 출력은 flag로 판단
느낀점
- 진짜 오랜만에 푸니까 인풋 받는 데에도 너무 오래 걸렸다.
- 이제 마지막 프로젝트가 끝났으니 매일매일 알고리즘 풀어야지.
- 같은 문제를 자바로도 풀어보면서 감 익혀야겠다.
'알고리즘 > 🥈 실버' 카테고리의 다른 글
백준 1926 그림 자바 풀이 (0) | 2023.12.17 |
---|---|
백준 1384 메시지 자바 풀이 (0) | 2023.12.15 |
백준 11659 구간 합 구하기 4 자바 풀이 (0) | 2023.08.20 |
백준 1138 한 줄로 서기 자바 풀이 (0) | 2023.07.26 |
백준 3273 두 수의 합 자바 풀이 (0) | 2023.07.24 |