[BOJ] 백준 10157 자리배정 (Swift)

문제

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

10157번: 자리배정

풀이

가로와 세로 길이에 따른 규칙을 구할 수는 없었습니다.

가로 세로가 최대 1,000 이므로 1,000 * 1,000 = 1,000,000으로 완전탐색으로 시간내에 풀이할 수 있다고 생각해
직접 좌석을 배정해 주는 방식으로 풀어야겠다고 생각이 들었습니다.

대기번호가 가로 * 세로 보다 크다면, 좌석을 배정할 수 없는 경우입니다.

아니라면, 2차원 배열을 사용하여 0,0 부터 자리를 지정해 줍시다.
뱡향은 시계방향이며, 북 동 남 서 방향입니다.

문제에서는 왼쪽 하단부터 0,0 이지만 저희는 편의성을 위해 왼쪽 상단부터 0,0으로 좌표를 설정해줍시다.
또한 남 동 북 서 로 방향을 바꿔주어야 합니다.

2차원 배열을 0으로 초기화 시켜주고,
배열의 크기를 벗어나지 않고, 배열의 원소가 0이라면 지나갈 수 있는 경우겠죠?
그런 경우 현재 방향으로 이동시켜줍시다.

배열의 크기를 벗어나거나, 배열의 원소가 0이라면?
방향을 바꿔줍시다.

2차원 배열의 원소를 하나씩 채우면서
입력받은 대기번호를 지정할 때, x 값과 y값을 출력해줍시다.

소스코드

	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let c = input[0], r = input[1]
	let target = Int(readLine()!)!
	var graph = [[Int]](repeating: [Int](repeating: 0, count: c), count: r)
	// 남 동 북 서
	let dx = [0, 1, 0, -1]
	let dy = [1, 0 ,-1, 0]
	// 범위를 벗어나는지 확인
	func isValidCoord(y: Int, x: Int) -> Bool {
	return 0..<r ~= y && 0..<c ~= x
	}
	var num = 1
	var i = 0
	var y = -1
	var x = 0
	// 대기번호가 가로 * 세로 보다 크다면, 좌석을 배정할 수 없는 경우
	if target > c * r {
	print(0)
	} else {
	// 대기번호를 모두 채울때 까지 반복
	while num <= c * r {
	var ny = y + dy[i]
	var nx = x + dx[i]
	// 범위를 벗어나거나, 이미 좌석을 배정한 경우 방향 변경
	if !(isValidCoord(y: ny, x: nx) && graph[ny][nx] == 0) {
	i = (i + 1) % 4
	ny = y + dy[i]
	nx = x + dx[i]
	}
	// 좌석 지정
	graph[ny][nx] = num
	// 입력으로 제시된 대기번호를 채웠다면 좌표 출력
	if num == target {
	print(nx + 1, ny + 1)
	break
	}
	// 다음 대기번호 채우기
	num += 1
	y = ny
	x = nx
	}
	}

view raw 자리배정.swift hosted with ❤ by GitHub

후기

좌석을 채우는 시뮬레이션 문제입니다.
범위를 벗어나거나 이미 좌석번호를 채웠다면 방향을 바꿔주는 부분에서 신경을 써야했던 문제입니다.