[Python] BOJ(백준) 17129번 - 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유

1. 링크

https://www.acmicpc.net/problem/17129

2. 난이도(solved.ac 참고)

골드5

3. 풀이

	# https://www.acmicpc.net/problem/17129
	import sys
	from collections import deque
	input = sys.stdin.readline
	q = deque()
	n, m = map(int, input().split())
	island = [list(map(int, list(str(input().rstrip())))) for _ in range(n)]
	visited = [[0 for _ in range(m)] for _ in range(n)]
	dx = [-1, 1, 0, 0]
	dy = [0, 0, -1, 1]
	def bfs(x, y):
	flag = False
	q.append([x, y])
	visited[x][y] = 1
	while q:
	if flag:
	break
	x, y = q.popleft()
	for i in range(4):
	nx = x + dx[i]
	ny = y + dy[i]
	if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and island[nx][ny] != 1:
	visited[nx][ny] = visited[x][y]+1
	q.append([nx, ny])
	if island[nx][ny] == 3 or island[nx][ny] == 4 or island[nx][ny] == 5:
	flag = True
	count_result = visited[nx][ny]-1
	break
	if flag:
	print("TAK")
	print(count_result)
	else:
	print("NIE")
	for i in range(n):
	for j in range(m):
	if island[i][j] == 2:
	bfs(i, j)

view raw 윌리암슨.py hosted with ❤ by GitHub

일반적인 BFS문제중 하나이다. visited를 방문 여부와 + 그 지점까지의 거리를 구하는 용도로 사용했다. visited를 1부터 시작했기 때문에 실제로 답을 낼 때는 -1을 해줘야한다. 왜냐면 다음 지점을 방문할 때마다 1씩 증가하게 해야하는데 그러면 0부터 시작해야되지만 그렇게 하면 not visited[nx][ny]에 걸려서 25행의 if문을 통과할 수 있기 때문이다.

 

근데, PyPy로 제출했을 때는 통과했는데 Python으로 제출하니까 시간초과가 떴다. 대체 왜..? 하고 보니까, Python3으로 맞은 사람이 단 한명도 없었다. 이 문제 한정 PyPy만 통과할 수 있다는 점.. 흥미로운 문제였다.