21736.md

백준 21736번 헌내기는 친구가 필요해

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

---

코드 설명

• dfs 로 상하좌우 방향키를 만들어줘서 확인해주면서 P의 개수를 세어주면 된다. -> 단 방문 가능할 경우의 P 개수를 세어야 한다.
• visit을 통해 방문여부를 0과 1로 표시한다.

소스코드

• 메모리 : 36348 KB
• 시간 : 772 ms

import sys
from collections import deque

def in_range(x,y):
	return x >= 0 and x < n and y >= 0 and y < m

def dfs(x,y):
	q = deque()
	cnt = 0
	visit[x][y] = 1
	q.append((x,y))
	
	while q:
		cx, cy = q.popleft()
		for dx, dy in zip(dxs, dys):
			nx, ny = cx + dx, cy + dy
			if in_range(nx,ny) and not visit[nx][ny] and uni[nx][ny] != "X":
				if uni[nx][ny] == "P":
					cnt += 1
				visit[nx][ny] = 1
				q.append((nx,ny))
	
	return cnt	


n, m = tuple(map(int,input().split()))
uni = [sys.stdin.readline().strip() for _ in range(n)]
visit = [[0]*m for _ in range(n)]
dxs, dys = [0,0,1,-1], [1,-1,0,0]

current = [(i,j) for i in range(n) for j in range(m) if uni[i][j] == "I"]
x, y = current[0][0], current[0][1]

friend = dfs(x,y)
if friend:
	print(friend)
else:
	print("TT")

오답 노트

• for문 내에서 cx, cy = nx, ny로 다시 초기화해줬기 때문에 틀렸다. for문은 상하좌우 방향으로 이동하면서 다음 이동할 좌표를 q에 저장하는 역할을 한다.
• cx, cy는 위에서 q를 popleft할때 초기화시켜주므로 for문 내에서 초기화시켜주면 안된다.

오답 코드

import sys
from collections import deque

def in_range(x,y):
	return x >= 0 and x < n and y >= 0 and y < m

def dfs(x,y):
	q = deque()
	visit = [[0]*m for _ in range(n)]
	cnt = 0
	dxs, dys = [0,0,1,-1], [1,-1,0,0]
	q.append([x,y])
	
	while q:
		cur = q.popleft()
		cx, cy = cur[0], cur[1]
		visit[cx][cy] = 1
		for dx, dy in zip(dxs, dys):
			nx, ny = cx + dx, cy + dy
			if in_range(nx,ny) and not visit[nx][ny] and uni[nx][ny] != "X":
				if uni[nx][ny] == "P":
					cnt += 1
				visit[nx][ny] = 1
				q.append([nx,ny])
				cx, cy = nx, ny
	
	return cnt	


n, m = tuple(map(int,input().split()))
uni = [sys.stdin.readline().strip() for _ in range(n)]
current = [(i,j) for i in range(n) for j in range(m) if uni[i][j] == "I"]
x, y = current[0][0], current[0][1]

friend = dfs(x,y)
if friend:
	print(friend)
else:
	print("TT")